문제
A=1, B=2, ..., Z=26으로 암호화된 숫자열이 주어졌을 때, 가능한 해석(디코딩) 방법의 수를 구하라.
입력
첫째 줄에 숫자로 이루어진 암호가 주어진다 (길이 1 이상 5,000 이하).
출력
해석 방법의 수를 1,000,000으로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
25114 | 6 |
풀이
DP로 한 자리/두 자리 해석 경우를 누적한다.
dp[i]를 i번째까지의 해석 수로 정의하고dp[0] = 1로 초기화한다- 현재 자릿수가 1~9이면 한 자리 해석 가능:
dp[i] += dp[i-1] - 이전 자릿수와 합쳐 10~26이면 두 자리 해석 가능:
dp[i] += dp[i-2] - 0은 단독 해석 불가하므로, 앞자리와 합쳐야만 유효하다
dp[N] % 1,000,000을 출력한다
핵심 아이디어: 피보나치 수열과 유사한 점화식이지만, 숫자 0과 27 이상의 조합 등 유효하지 않은 경우를 제외해야 한다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day356BOJ2011암호코드 {
static final int MOD = 1_000_000;
static int N, n, nn, t;
static char[] c;
static int[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
c = br.readLine().toCharArray();
N = c.length;
dp = new int[N + 1];
dp[0] = 1;
for (int i = 1; i < N + 1; i++) {
n = c[i - 1] - '0';
if (0 < n && n < 10) {
dp[i] += dp[i - 1];
dp[i] %= MOD;
}
if (i == 1)
continue;
nn = c[i - 2] - '0';
if (nn == 0)
continue;
t = nn * 10 + n;
if (9 < t && t < 27) {
dp[i] += dp[i - 2];
dp[i] %= MOD;
}
}
System.out.println(dp[N]);
}
}복잡도
- 시간: O(N) - 한 번의 순회
- 공간: O(N) - DP 배열