본문 바로가기
728x90

다이나믹 프로그래밍35

[JAVA]백준 9252번: LCS 2 www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 두 문자열의 최장 공통부분 수열의 길이를 출력하고 최장 공통부분 문자열을 출력한다. 2. 풀이 LCS(최장 공통부분 수열)의 길이를 구하고 역추적하여 최장 공통부분 문자열을 출력하는 문제이다. 혹시 LCS의 길이를 구하는 것부터 막힌다면 아래 문제를 먼저 풀어보는 걸 추천한다. www.acmicpc.net/problem/9251 9251번: LCS.. 2021. 2. 7.
[JAVA]백준 12852번: 1로 만들기 2 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 문제 설명 정수 X에 사용할 수 있는 연산이 3가지가 있다. X/2, X/3, X-1 위의 세가지 연산을 사용하여 주어진 정수 N을 1로 만들려고 할 때 연산을 사용하는 횟수의 최솟값과 1로 만드는 방법을 출력하는 문제이다. 2. 풀이 DP를 이용해서 최솟값을 구하고 그 순간들의 선택을 배열로 저장하여 역추적할 수 있다. dp 배열에는 현재 정수 N을 1로 만들 수 있는 최솟값을 저장하고 trace 배열에는 연산을 사용하였을 때 N 전의 값이 무엇인지 저장한다. X/3 연산을 사용하여 연산 횟수의 최솟값을 구하.. 2021. 2. 5.
[JAVA]백준 2096번: 내려가기 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 설명 N 줄에 0 이상 9 이하의 숫자가 세 개씩 적혀있을 때 첫 줄에서 마지막 줄까지 내려가면서 얻을 수 있는 최대 점수, 최소 점수를 출력하는 문제이다. 내려가는 방법은 3가지가 있는데 아래 그림과 같다. 2. 풀이 메모리 제한이 있으나 신경 쓰지 않아도 풀 수 있는 문제이다. [N][3] 크기의 max와 min 배열을 만든 후 가능한 값들을 하나씩 더해가면서 max와 min 배열을 채워나가면 되는 간단한 문제.. 2021. 2. 1.
[JAVA]백준 2602번: 돌다리 건너기 www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 문제 설명 돌다리 2개가 주어지고 마법의 두루마리 문자열이 주어졌을 때 마법의 두루마리 문자열의 순서대로 돌다리를 건너야 한다. 돌다리 건너는 규칙은 네 가지가 있는데 1. 왼쪽에서 오른쪽으로 이동하며, 주어진 마법의 두루마리 문자열에 적힌 순서대로 모두 밟고 가야 한다. 2. 돌다리 2개를 번갈아 가면서 건너야 한다. 3. 건너뛰는 칸의 수는 상관이 없다. 4. 한 칸 이상 오른쪽으로 전진해야 한다. 문자열과 돌다.. 2021. 1. 29.
728x90

티스토리툴바