Dynamic Programming 복습2 (백준 2011번, 암호코드)

출처
https://www.acmicpc.net/problem/2011
 
문제



변수 설명
- n: 각 digit이 저장되어 있는 int array .
- dp: 암호의 각 자리 수까지 나올 수 있는 해석의 수를 저장하는 array(암호가 없을 때도 추가 했기 때문에 index의 length는 n.length +1임.

점화식 설명
- 암호가 한 자리일 때와 두 자리일 때를 구분해야 함.
- 암호가 '1'부터 시작하기 때문에 '0'일 때는 '암호 한 자리'일 때를 적용할 수 없음. digit이 '0' 아닐 때만, 암호해석의 경우의 수를 +1 해줌. (dp[i] = dp[i-1])
- 암호가 두 자리일 경우는, 두자리를 읽었을 때 그 수가 10 이상 26이하여야 함. 그 조건에 만족하면 그 두자리를 읽기 전까지의 암호해석 수에 한 자리로 암호 해석을 하는 경우의 수를 더해 주어야 함. ( dp[i] = dp[i-2] + dp[i])
- 선제 조건: dp[0] = 1. dp[1] = 1 ( 암호가 없을 경우와 첫번째 암호 digit을 읽었을 경우는 각각 암호 해독 방법이 1가지 씩 임)

코드
- bottom-up으로 풀었음.