다이나믹 문제를 유형별로 분류해 보면,
1. 단순 1차원
1.1로 만들기(백준 1463)
1.2 피보나치 수열
1.3 파스칼의 삼각형
2. 2차원
2.1 LCS(Lognest Common Subsequence)
2.2 집합(최소차)
3. 냅섹류 2차원
3.1 배낭
4. 3차원
4.1 롤러코스트(소가 만드는)
5. 이진분류
5.1 피보나치의 0, 1 리턴 횟수 (백준 1003번 문제)
5.2 이친수 (백준 2193번)
5.3 인접한 비트의 수
6. 부분합, 최대/최소
6.1 동전1 (백준 2293번)
6.2 포도주 시식 (백준 2156)
6.3 막대기(N종류, 총길이 K)
6.4 합분해 (K번사용 합N 경우수)
6.5 돌다리 건너기(RINGSR)
6.6 마트료시카
6.7 붕어빵 판매하기(백준 11052, 붕어빵 세트 최적판매)
7. 그래프/자료구조 연계
7.1 폐지줍기
8. 기타
8.1 조약돌 놓기 (쉽게 배우는 알고리즘 8장)
----------------------------------------------
1. 단순 1차원
1.1 1로 만들기(백준 1463)
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.
풀이
- 3으로 나눌 수 있으면 3으로 나누는 것이 이익. 그러나, 2로 나눌 수 있는 경우는, 1을 뺀 후 3으로 나눌 수 있는 경우와 비교해봐야 한다. 이 경우도 3으로 나눌 수 있다고 해서 무조건 해야하는 것은 아니다. (예를 들어 16의 경우, 16->8->4->2->1의 경우가, 16->15->5->4->2->1보다 짧다.)
해서, -1을 하는 경우, 2로 나누는 경우, 3으로 나누는 경우 중 가장 최솟값을 가지게 DP 해야 함
- D[i]: 숫자 i에 대해서 최소 연산 횟수
D[i] = min(D[i-1]+1, (i%2==0) ? D[i/2], (i%3==0) ? D[i/3])
D[1]=1, D[2]=1, D[3]=1
1.2 피보나치 수열
0 1 1 2 3 5 8 13 ...
D[0] = 0
D[1] = 1
D[i] = D[n-2] + D[n-1]
1.3 파스칼의 삼각형
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...
D[i][j] = (j==0 || j==i) ? 1 : D[i-1][j-1] + D[i-1][j]
1.3 2 x n 타일일 (1)
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
D[i] = D[i-1] + D[i-2]
이전 경우에서 막대 한 개를 추가하는 것과, 이전이전에서 (1x2)막대 2개를 채우는 방법의 합
즉, N번째에서 생각해보면, 1)N번째에 2x1타일이 있는 경우 2)N-1과 N에 걸쳐서 1x2 타일 2개가 있는 경우가 있기에.
1.4 2 x n 타일링 (2)
2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
D[i] = D[i-1] + 2 * D[i-2]
이전 경우에서, 막대 한개를 추가하는 방법이 있고, 이전이전에서는 두 가지 방법이 있기에.
즉, 1)N번째에 (2x1)타일 1개가 있을 수 있고 2)N-1에서 N까지 (1x2)타일 2개 3)N-1에서 N까지 2x2 타일 1개 있는 경우 있음.
2. 2차원
2.1 LCS(Lognest Common Subsequence) (백준 9251)
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다
풀이
Xm=<x1 x2 ... xm> Yn=<y1 y2 yn>
D[i][j] : X의 i번째 길이까지, Y의 j번째 길이 까지의 LCS 길이
D[i][j] = D[i-1][j-1] + 1, when xi == yi
= max(D[i-1][j], D[i][j-1], when xi != yj
D[i][0] = 0, D[0][j]=0
2.2. 집합
집합 A와 B에 각각 N, M개의 자연수가 들어있다. 이제 다음의 행동을 min(N, M)번 시행할 것이다.
집합 A, B에서 각각 자연수 하나씩 고르고, 고른 수는 각 집합에서 삭제한다
고른 두 수의 차를 집합 C에 넣는다.
우리의 목표는 집합 C에 있는 원소의 합을 최소로 하는 것이다.
핵심
- 두 집합을 소팅
- 같이 차례대로 빼내야 함.
D[i][j] : A에서 1~i까지, B에서 1~j까지 사용했을 때, 최소 합
D[i][j] = D[i-1][j-1] + abs(A[i] - B[j])
if(i>j && D[i][j] > D[i-1][j]) D[i][j] = D[i-1][j]
if(i<j && D[i][j] > D[i][j-1]) D[i][j] = D[i][j-1]
3. 냅섹류 2차원
3.1 배낭
n개의 보석이 있다. 각 보석은 자신의 고유 무게와 가치가 있다. 배낭에 이 보석들을 담는데, 보석들의 가치 총계가 최대가 되게끔 담아라. 단, 배낭에 담을 수 있는 최대무게는 제한되어있다. 즉, 제한된 무게내에서 최대가치가 되게 보석들을 담아야 한다. (담을 수 있는 개수는 제한이 없다.)
핵심 아이디어: i번째 보석을 담거나 안담거나의 두가지 경우로 나눠서, 그 두가지 중 최대값 취함
w[i]: i번째 보석의 무게, v[i]:i번째 보석의 가치
D[i][j] : 0~i번째까지의 보석을 사용하고, j무게 만큼의 제한이 있을 때, 취할 수 있는 최대 보석 가치
D[i][j] = (w[i] < j) ? max(D[i-1][j], D[i-1][j-w[i]] + v[i]) : D[i-1][j]
D[0][j]=0
4. 3차원
4.1. 롤러코스트 (백준 6208)
소들은 롤러코스터를 짓고있다! 소들은 자신들이 가지고 있는 돈을 활용해서 최대한 재밌는 롤러코스터를 만들고 싶어한다.
롤러코스터는 길이 L(1<=L<=1,000)의 직선형 롤러코스터이다. 소들이 롤러코스터를 지을 때 롤러코스터는 N(1<=N<=10,000)개의 교체 가능한 부품들중 일부로 구성되어야 한다.
각 부품i는 고정된 길이 Wi(1<= Wi <= L)를 가지고 있다. 그리고 다양한 지형의 굴곡 때문에, i번째 부품은 오직 Xi(0<= Xi <= L-Wi)의 위치를 시작점으로만 놓을 수 있다.
소들은 다양한 롤러코스터를 0부터 L까지 빈틈없이 채우고 싶어한다. 만약 중간에 빈칸이 있으면 롤러코스터를 구성할 수 없다. 또한 각 부품끼리 겹쳐서 롤러코스터를 건설하는 경우도 없다.
각 i번째 부품은 "재미도" Fi(1<= Fi <= 1,000,000)과 짓는데 드는 비용 Ci(1<= Ci <= 1000)를 가지고 있다. 총 비용은 롤러코스터를 구성하는 부품을의 비용의 합으로 계산된다. 마찬가지로 총 재미도의 합은 롤러코스터를 구성하는 부품들의 재미도의 합으로 계산된다.
소들의 총 예산은 B(1<= B<= 1000)이다. 소들을 도와 예산내에서 가장 큰 재미도를 가진 롤러코스터를 지을 수 있도록 도와주자!
M[i][k]: i가 끝점인 곳에 위치한 k번째 부품 {x,f,c}
D[i][j]: i 길이 까지, j예산내에서 만들 수 있는 최대 재미값
D[i][j]=-1
newVal = D[M[i][k].x][j-M[i][k].c] + M[i][k].f
D[i][j] = (D[i][j]==-1 || D[i][j] < newVal) ? newVal
where
j > M[i][k].c
D[i-M[i][k].x][j-M[i][k].c] != -1
ans = max(D[L][i])
5. 이진분류
5.1 피보나치의 0, 1 리턴 횟수 (백준 1003번 문제)
피보나치 수를 재귀로 푸는 프로그램코드가 있을 때, N이 주어졌을 때 0과 1이 리턴되는 횟수를 구하시오.
풀이.
핵심 아이디어: f[N] =f[N-1] + f[N-2]이기에, f[N]에서 1과 0이 리턴되는 수는, [N-1]과 [N-2]에서 1과 0이 리턴되는 수와 같음
D[i][j] : 숫자 i에 대해서 j가 리턴되는 회수. 이 때 j=0 or 1
D[i][0] = D[i-1][0] + D[i-2][0]
D[i][1] = D[i-1][1] + D[i-2][1]
D[0][0] = 1, D[0][1] = 0
D[1][0] = 0, D[1][1] = 1;
5.2 이친수 (백준 2193번)
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1≤N≤90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
풀이
D[i][0]: 0으로 끝나며, i자리인 이친수 개수
D[i][1]: 1으로 끝나며, i자리인 이친수 개수
D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]
D[0][0] = D[0][1] = 0
D[1][0] = 0, D[1][1] =1
5.3 인접한 비트의 수 (백준 2698)
0과 1로 이루어진 수열 S가 있다.
S의 첫 수를 s1, 마지막 수를 sn이라고 할 때, S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.
s1 x s2 + s2 x s3 + s3 x s4 + ... + sn-1 x sn
위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.
수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.
예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.
11100, 01110, 00111, 10111, 11101, 11011
D[i][j][0] : 0으로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[i][j][1] : 1으로끝나면서, i개의 비트를 사용해서, j개의 인접비트수가 되는 수열 개수
D[1][0][0] = D[1][0][1] = 1
2 <= i <= n, 0 <= j < i
D[i][j][0] = D[i-1][j][0] + D[i-1][j][1]
D[i][j][1] = D[i-1][j][0] + D[i-1][j-1][1]
6. 부분합, 최대/최소
6.1 동전1 (백준 2293번)
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)
풀이
D[i][j] : 동전 i개를 써서, j원이 되게하는 경우의 수
P[i]: i번째 동전의 가치
D[i][j] = Sum(D[i-1][j-k*P[i]]), 0 <= k <= j/P[i]
D[1][0]=1
6.2 포도주 시식 (백준 2156)
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
풀이
- D[i] : i번째 포도주까지 최댓값
- 제일 마지막 포도주를 기준으로 해서, 아래 3가지 경우 중 최댓값.
1)안마시는 경우 D[i-1]
2)마시고, n-1 번째것을 마신 경우: V[i] + V[i-1] + D[i-3]
3)마시고, n-1번째것을 안 마신 경우: V[i] + D[i-2]
cf)유사문제로 계단 문제가 있는데, 이 경우 제일 마지막 계단은 무조건 밟는 것으로, 포도주 문제와 약간 다름. 계단 처럼 무조건 마지막 계단을 밟는 경우는, 위의 2번 3번 케이스만 고려하면 됨
6.3. 막대기
n가지 종류의 막대기가 있다. 막대기의 길이는 모두 다르다. 이 막대기들을 적당히 사용해서, 총 길이가 K가 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 막대기는 여러번 사용할 수 있다.)
입력
첫째 줄에 n,k 가 주어진다. (1 <= n <= 100, 1 <= k <= 10,000) 다음 n개의 줄에는 각각의 막대기의 길이가 주어진다.
출력
첫째 줄에 경우의 수를 출력한다. 1000000으로 나눈 나머지를 출력하시오.
풀이
- n개가 아닌, n종류라는 데 주의. 즉, 1종류를 여러번 사용 가능
- D[i][j]: i개까지의 막대기를 이용해서, j 길이 만큼을 만들 수 있는 경우의 수
- D[0][0]=1 ==> 0개의 막대기를 이용해서 길이 0만큼 만들 수 있는 경우의 수
D[i][j] = Sum(D[i-1][j - k x s[i]), 0 <= k <= j/s[i]
==> i개까지 막대기를 사용해서 j길이만큼을 만들 수 있는 경우의 수는,
한 개 덜 사용하면서(i-1개 사용하면서), i번째 막대기를 0번사용~j/s[i]번까지 사용할 때의 경우의 수를 모두 합한 것.
즉, i번째 막대기를 안 사용할 수도 있고, 1개 사용할 수도 2개 사용할 수도 있는 것.
최대 몇개까지 사용할 수 있는 가는, j - k x s[i] > 0 이므로, k <= j/s[i] 일 때까지.
6.4. 합분해
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1≤N≤200), K(1≤K≤200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
- D[K][N]을 구하는 것. 숫자를 K개 더해서 그 합이 N이 되는 경우의 수
- D[i][j]: 숫자를 i개 더해서, 그 합이 j가 되는 경우의 수
- D[i][j] = D[i-1][j] + D[i-1][j-1] + ... +D[i-1][0]
==> i개 더해서 합이 j가 되는 경우의 수는, i-1개 사용해서 j가 된 후 0을 더하거나(i번째 수로 0을 선택), i-1개 사용해서 합이 j-1인 상태에서 i번째로 1을 사용하거나, j-2에서 2를 사용하는 등의 조합이 가능(수는 0~j까지 존재하니깐)
- D[0][0]=1 ==> 숫자 0개를 더해서 그 합이 0이되는 경우의 수는 1
6.5 돌다리 건너기
절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 <악마의 돌다리>이로 다른 하나는 <천사의 돌다리>이다.
아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고, 아래의 가로줄은 <천사의 돌다리>를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.
R I N G S R
G R G G N S
반지원정대가 소유하고 있는 마법의 두루마리에 <악마의 돌다리>와 <천사의 돌다리>를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져 반지원정대는 화산 속으로 떨어지게 된다.
다리를 건널 때 다음의 제한 조건을 모두 만족하면서 건어야 한다.
1) 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.
2) 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.
3) 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1고 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 크게 표현된 문자는 밟고 지나가는 돌다리를 나타낸다.)
풀이
An = 목표 문자열
Bm : 천사 돌다리
Cm : 악마 돌다리
D[i][j][0] : 천사돌다리로 끝나면서, i번째 목표문자열까지, j번째 돌다리문자를 이용해서 만들 수 있는 최대 경우 수
D[i][j][1] : 악마돌다리로 끝나면서, ...
if(A[i] == B[j]) //목표문자열 i번째와 천사돌다리 j번째가 같다면
D[i][j][0] = Sum(D[i-1][k][1]), 0<= k <= j-1 // (j-1)까지의 악마돌다리에서의 경우의 수 합
if(A[i] == C[j]) //목표문자열 i번째와 악마돌다리 j번째가 같다면
D[i][j][1] = Sum(D[i-1][k][0]), 0<= k <= j-1 // (j-1)까지의 천사돌다리에서의 경우의 수 합
D[0][0][0] = D[0][0][1] = 1
//0번째 목표문자열, 0번째 돌다리문자 이용 경우의 수로, 1의 의미가 좀 약하지만,
//이렇게 해야 위의 점화식의 Sum값이 제대로 동작
ans = Sum(D[n][k][0] + D[n][k][1]), 1<= k <=m //모두 더해줌에 유의. 달랑 D[n][m][0] + D[n][m][1] 이 아님
//돌다리의 끝까지인 m까지 사용안하고도, 목표문자열을 만족시킬 수 있기 때문
//D[i]: 붕어빵 i개에 대한 최적해. D[N]=? D[1] = p[1]; for (int i = 2; i <= N; ++i) for (int j = 0; j < i; ++j) D[i] = max(D[i], D[j] + p[i - j]); printf("%d\n", D[N]);7. 그래프/자료구조 연계
7.1. 폐지줍기
N * N 격자로 이루어진 도시가 있다. 이 도시 군데군데에는 폐지가 버려져 있다.
범수는 가장 왼쪽 위 격자 (1,1)에서 출발하여 가장 오른쪽 아래 격자 (N,N)까지 이동하며 폐지를 줍는데, 최단 경로를 따라가야만 한다. 즉, 인접한 오른쪽 칸 또는 아래쪽 칸으로만 이동할 수 있다. 이 때, 범수가 수집할 수 있는 폐지의 최대값을 출력하시오.
출발점과 도착점에 위치한 폐지 또한 주울 수 있다.
풀이
- D[i][j] : (i,j)칸에서의 폐지 최대값
D[1][1] = a[1][1]
D[i][j] = max(D[i][j-1], D[i-1][j]) + a[i][j]
==> a[i][j] += max(a[i][j-1], a[i-1][j] 로도 가능
8. 기타
8.1 조약돌 놓기 (쉽게 배우는 알고리즘 8장)
3 x n 테이블의 각 칸에 숫자가 쓰여 있다. 테이블에 칸들 중 일부에 제한조건을 만족하는 방법으로 조약돌을 놓아 조약돌이 놓인 곳에 있는 수의 합을 최대로 하시오.
- 가로나 세로로 인접한 두 칸에 동시에 조약돌이 놓일 수 없다.
- 각 열에는 하나 이상의 조약돌을 놓는다.
풀이
- 1~i열까지의 최대합을 고려해보면, i열에 대해서, 다음과 같은 4가지 패턴으로 분류할 수 있다.
i 열 (i-1)열
1)1행 값이 선택된 경우 max(패턴2, 패턴3) + 1행값
2)2행 max(패턴1, 패턴3) + 2행값
3)3행 max(패턴1, 패턴2) + 3행값
4)1행과 3행 패턴2 + 1행값 + 3행값
- D[i][p] : i열이 패턴 p로 놓일 때의 최고 점수
W[i][p] : i열이 패턴 p로 놓일 때, i열에 돌이 놓인곳의 점수 합 ->테이블값으로부터 미리 구해둔다.
- D[i][p] = max(D[i][q] + W[i][p] , i>=2 , q:p와 양립하는 패턴
D[1][p] = W[1][p]
- 슈도코드
for(i=2 to n)
for(p=1 to 4)
D[i][p] = max(D[i][q]) + W[i][p]
return max(D[n][p]), p:1~4
-끝-