안녕하세요 이번 시간에는 저번 시간에 이어서 DP 문제의 유형 분석을 해보도록 하겠습니다.
세 번째 유형은 특정 조건을 만족하는 수열의 개수(경우의 수)를 구하는 문제입니다. 이 문제의 경우 최대 최소를 구하는 문제와 더불어 DP에서 가장 많이 나오는 유형 중 하나로 이전 항과의 점화식으로 푸는 유형과 현재 항을 누적해서 너하는 방법으로 풀 수 있습니다.
백준 2193(이친수) 문제의 경우 0으로 시작하지 않으며 1이 두 번 연속 나타나지 않는 이진수인 이친수으 개수를 구하는 문제입니다. 이진수 특성 상 0과 1 두 개만 존재하기 때문에 dp[i][0] : i 길이에서 끝이 0으로 끝나는 이친수 개수, dp[i][1] : i 길이에서 끝이 1로 끝나는 이친수 개수로 설정합니다. 0으로 끝나면 뒤에 0이나 1 둘 다 와도 상관 없으나 1로 끝나면 반드시 0만 와야 하기 때문에
--> dp[i][0] = dp[i-1][0] + dp[i-1][1]
—> dp[i][1] = dp[i-1][0]
로 설정해줍니다. 여기서 주의할 점은 N이 최대 90이기 때문에 90자리의 이친수 개수는 long 범위까지 넘어가기 때문에 int 대신 long으로 dp 배열을 설정해줍니다.
백준 10844(쉬운 계단 수) 문제의 경우 인접한 모든 자리의 차이가 1인 계단 수의 개수를 구하는 문제입니다. 이 문제 역시 이친수 문제와 마찬가지로 종료되는 값을 기준으로 dp[i][j] : 자릿수가 i인 수 중 j 높이로 종료되는 계단 수를 만들 수 있는 경우의 수로 설정해줍니다. 새롭게 추가되는 값은 마지막 값과의 차이가 1이어야 하기 때문에 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]로 설정하되 j-1이 1보다 작다면 더하지 않고 j+1이 9보다 크다면 더하지 않습니다. 이렇게 구한 dp 배열을 j를 0부터 9까지 모두 더한 합을 출력합니다. 여기서 주의할 점은 dp[i-1][j-1] + dp[i-1][j+1] 자체가 값이 클 수 있기 때문에 이 부분을 문제에서 주어진 값으로 나눈 나머지로 계산하고, 또한 최종 정답을 구할 때에도 더한 값을 한번 더 나눈 나머지로 출력합니다.
백준 1904(01타일) 문제의 경우 1 하나와 0 두개를 이용해서 크기가 N인 이진 수열의 가짓수를 구하는 문제입니다. dp[i] : 길이가 i인 이진 수열의 가짓수로 설정하면 i-1 길이는 가지는 경우는 1 하나를 추가하는 경우밖에 없으며 i-2 길이의 경우 0 두개를 추가하는 경우밖에 없습니다. 1 두개를 추가하는 경우는 i-1 길이 가짓수에 포함되기 때문에 고려하지 않습니다. 따라서 dp[i-1] + dp[i-2]로 설정하여 dp[N]을 출력합니다.
백준 11057(오르막 수) 문제의 경우 수의 자릿수가 N일 때 수의 자리가 오름차순을 이루는 수의 개수를 구하는 문제입니다. 이 문제 역시 마지막 자리 수를 기준으로 dp[i][j] = 마지막 자리가 j이고 자릿수가 i인 오르막수 개수로 설정합니다. 각 자리수가 오름차순을 이루기 때문에 i-1 길이의 수 중 j보다 작은 수로 끝나는 수들의 가짓수를 모두 더해줍니다. 즉 dp[i][j] += dp[i-1][j-k] k = 0부터 j까지로 설정합니다. 이후 dp[N][0] 부터 dp[N][9]까지의 합을 구하고 10007 나머지 연산을 진행합니다. 여기서 주의할 점은 dp 배열을 계속 합하는 구조이기 때문에 초기값을 0으로 설정해야 값의 오류가 없게 됩니다.
