[백준 02011] 암호코드 [Java]

문제

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

---

풀이

대문자 알파벳을 1 ~ 26으로 암호화한 문자열에 대해 해석 가능한 경우의 수를 출력하는 문제다.

우선 주어진 입력의 유효성부터 판별해보자.

입력이 0인 경우 암호를 해석할 수 없다. 0을 출력하고 종료하자.

 

이제 점화식을 세워보자.

dp[i] : i번째 까지 해석 가능한 경우의 수

• N이 1의 자리인 경우, dp[1] = 1
• 탐색 대상의 수( N[i - 1] )가 0보다 크다면, 기존 경우의 수만큼 가질 수 있다. dp[i] = dp[i - 1]
• N[i - 2], N[i - 1]로 이루어진 두 자릿수가 10 이상, 26이하라면, 두 수를 하나의 수로 볼 수 있다. dp[i] = (dp[i] + dp[i - 2]) % MOD

---

소스코드

보기