dp :: 백준 :: 암호코드 :: 2011

암호코드

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

언뜻 보면 쉬운 dp문제처럼 보이는데.. 예외로 처리해줘야 할 사항들이 몇가지 있다.

나는 그 사항들을 체크하지 않아 엄청 많이 틀렸다.

주어진 입력이 해석 가능한 숫자조합인지 꼭!!! 체크한 뒤 제거해 줘야 한다.

체크해줘야할 사항들로는

1. 0으로 시작하는 경우

2. 0이 연속으로 나오는 경우

3. 0 앞에 3~9의 숫자가 나오는 경우

4. 그리고!! 출력은 10000000으로 나눈 나머지를 출력할것! 잊지말자.

이 모든 예외들을 처리해 준 후 

dp[i] = dp[i-1] + dp[i-2](S.charAt(i) > '0' && (S.charAt(i-1) == '1' || ( S.charAt(i-1) == '2' && S.charAt(i) < '7'))을 만족하는 경우)

위와 같은 점화식으로 모든 연산을 마친 후

최종 값을 출력해주면 된다.