[백준] 2011번 : 암호코드

문제

 

 

접근 방식

각 자리의 수마다 경우의 수를 이전 자리의 수들을 활용해가며

DP 테이블을 채워주면 되는 간단한거 같은 문제지만

예외 케이스가 머리를 아프게 한다.

 

우선 11111111과 같은 일반적인 경우를 살펴보겠다.

1	1	1	1	1	1	1	1
1
	2
		3
			5
				8
					13
						21
							34

 

위의 표는 첫 자리부터 각 자리수마다 만들 수 있는 경우의 수로

3번째 자리의 수에 올 수 있는 경우의  수는

3번째 자리를 독립적으로 사용한 경우나

2번째 자리와 합쳐서 두 자리 수를 만든 경우를 합친 것으로

규칙을 찾아보면 피보나치의 점화식과 같은

dp[i] = dp[i-2] + dp[i-1] 인 것을 알 수 있다.

 

하지만 이건 모든 수들이 일반적일 때의 경우로

다음과 같이 조심해야 할 부분이 있다.

 

1. 0으로 시작하는 경우
2. 00인 경우
3. 26보다 큰 경우
4. 10 미만인 경우
5. 10, 20인 경우
6. 마지막 자리가 0이고 30 이상인 경우

 

0123456

 

첫 번째 경우부터 살펴보면

0이 처음에 등장하여 00이나 01 같은 잘못된 경우가 발생할 수 밖에 없다.

 

0이 중간에 등장한다면 10이나 20 같은 2자리 숫자로라도 만들 수 있지만

처음에 등장하면 앞에 붙여줄 숫자가 없으니 살릴 방법이 없다.

1001

 

다음은 0이 연속으로 등장하는 경우로

이건 당연히 무슨 수를 써도 정상적인 수를 만들 수 없다.

127

 

다음은 26보다 큰 숫자가 등장하는 경우로 위의 경우에는

1 + 2 + 7 과 12 + 7 두 가지 경우를 만들 수 있다.

 

1 + 27 같은건 만들 수 없기 때문에 dp[i-2]의 값은 필요가 없어

dp[i] = dp[i-1]이 된다.

109

 

마찬가지로 10보다 작은 0으로 시작하는 경우도

1 + 0 + 9는 불가능하고 10 + 9만 가능하니

dp[i-2]의 값은 필요가 없어 dp[i] = dp[i-1]이 된다.

1101
1201

 

다음은 10 혹은 20의 경우를 생각해보자

 

0은 무조건 이전의 숫자인 1이나 2와 합쳐야지만

정상적인 수로 존재할 수 있기 때문에

위의 두 경우와 반대로 dp[i-1]이 필요가 없어

dp[i] = dp[i-2] 가 된다.

130

 

그렇다면 마지막 자리가 0이고 30 이상이면 어떻게 될까?

 

0은 혼자서는 온전한 수가 될 수 없어 무조건 이전의 수와 합쳐야하는데

합쳐서 10이나 20이 된다면 상관 없지만 30, 40, ..., 90이라면

26이상의 수라 알파벳으로 바꿀 수 없는 수가 되버린다.

 

이는 잘못된 경우이기 때문에 0을 출력해줘야 한다.

 

위의 경우들을 모두 예외 처리 해주면서 테이블을 채워주기만 하면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String secret = br.readLine();

		if (secret.charAt(0) == '0') {
			System.out.println(0);
			return;
		}

		int len = secret.length();
		long[] dp = new long[len + 1];

		dp[0] = 1;
		dp[1] = 1;

		for (int i = 2; i <= len; i++) {
			int x = Integer.parseInt(secret.substring(i - 2, i));

			if (x == 0) {
				System.out.println(0);
				return;
			}

			if (i == len && x % 10 == 0 && x > 26) {
				System.out.println(0);
				return;
			}

			if (x > 26 && x % 10 == 0) {
				System.out.println(0);
				return;
			}

			if (x > 26 || x < 10) {
				dp[i] = dp[i-1];
			} else if (x % 10 == 0) {
				dp[i] = dp[i-2];
			} else {
				dp[i] = (dp[i-1] + dp[i-2]) % 1000000;
			}
		}

		System.out.println(dp[len]);
	}
}