알고리즘/DP
dp :: 백준 :: 암호코드 :: 2011
lingi04
2016. 12. 19. 22:53
언뜻 보면 쉬운 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'))을 만족하는 경우)
위와 같은 점화식으로 모든 연산을 마친 후
최종 값을 출력해주면 된다.