Hyun's_Devlog

https://www.acmicpc.net/problem/15991

다이나믹 프로그래밍 문제다.

풀이

우선 1부터 6까지 1,2,3을 이용한 대칭 수식을 생각하면 점화식을 위한 조건이 만들어진다.

7부터는 앞서 생각한 경우의 수식에 양쪽으로 1+...+1, 2+...+2, 3+...+3의 형태로 대칭으로 늘려나가면 된다.

즉 dp[num] = dp[num-2] + dp[num-4] + dp[num-6]이라는 점화식을 세울 수 있다.

7부터 100,000까지 반복문을 돌려 정답배열을 만든후 입력값을 인덱스로 정답을 출력하면 된다.

정답 코드

점화식을 세우는건 항상 어렵다..,

https://www.acmicpc.net/problem/2011

답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.

풀이

암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.

현재 암호가 0보다 크다면,
dp[i] += dp[i-1]
추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면,
dp[i] += dp[i-2]

점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.

정답 코드