2011번 - 암호코드

2024-10-01

#JAVA#백준

문제 링크

문제 풀이 시간 : 30분

문제 요약 :

•
A를 1, B를 2와 같이 Z까지 암호화를 한다.

•
암호화된 문장을 보고 해석할 수 있는 경우의 수를 구한다.

문제 풀이 :

이 문제는 딱 보자마자 dp로 풀어야 겠구나 라는걸 알 수 있었다.

근데 dp는 항상 그렇듯 dp라는 것은 알 수 있지만

어떤 방식으로 풀어야할지 생각하는데 더 오래 걸리는 것 같다.

예제를 보면서 이것저것 적어보다가 하나의 규칙성을 찾게 되었다.

예제와 같은 25114라는 암호문이 주어졌다고 할 때,

우리는 맨 앞에 한 칸이 있다고 생각하고 경우의 수를 생각하면 된다.

위 경우에서는 2는 한가지 경우만 있기 때문에 1이라는 경우의 수를 가지게 된다.

여기서 다음 암호인 5가 온다면 두가지 경우의 수가 생긴다.

그래서 처음에는 2의 경우의 수인 1에다가 2를 곱해줘야하나?

하고 끝까지 해보니

8 이라는 경우의 수가 나온다.

그래서 다시 다른 방식을 생각해보다가

갑자기 피보나치가 나의 뇌리를 스쳐갔다.

그랬더니 마법처럼 답이 나왔다.

먼저 이렇게 코드를 짜보았다.

초기 핵심 코드

Java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int n = input.length();
        input = '9' + input; //맨 앞에 임의의 수 넣어줌
        int[] dp = new int[input.length() + 1];
        dp[0] = 1; //첫번째 경우는 항상 1

        for (int i = 1; i <= n; i++) {
            if (input.charAt(i - 1) == '1') { //전의 수가 1이라면 현재 무슨 수가 와도 상관없음
                dp[i] = dp[i - 1] + dp[i - 2];
            } else if (input.charAt(i - 1) == '2') { //전의 수가 2라면 현재 6이하의 수가 와야함.
                if (input.charAt(i) <= '6') {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            } else { //두 경우 다 아니라면 전의 경우의 수 가져옴
                dp[i] = dp[i - 1];
            }
        }

하지만 이렇게 했더니 14%에서 틀렸다.

왜일까???

바로 현재 수가 0일 때,

다른 처리를 해주어야한다.

아래와 같은 경우가 있을 때,

0이 온다면 전에 1,2 만 올 수 있고,

1,2 가 있더라도 전의 경우의 수를 그대로 가져와야 한다.

Java

for (int i = 1; i <= n; i++) {
            if (input.charAt(i) == '0' && (input.charAt(i - 1) != '1' && input.charAt(i - 1) != '2')) {
                dp[n] = 0; //현재 수가 0인데 앞에 1,2가 아니라면 될 수 없는 경우
                break;
            } else if (input.charAt(i) == '0' && (input.charAt(i - 1) == '1' || input.charAt(i - 1) == '2')) {
                dp[i] = dp[i - 1]; //현재 수가 0이고 앞의 수가 1,2라면 경우의 수 그대로 가져옴
            } else if (input.charAt(i - 1) == '1') {
                dp[i] = (dp[i - 1] + dp[i - 2]);
            } else if (input.charAt(i - 1) == '2') {
                if (input.charAt(i) <= '6') {
                    dp[i] = (dp[i - 1] + dp[i - 2]);
                } else {
                    dp[i] = dp[i - 1];
                }
            } else {
                dp[i] = dp[i - 1];
            }
        }

이렇게 해주었더니

결과는?

또 틀렸다

왜???

아래의 경우를 보자.

현재 코드에서는 0이 왔기 때문에 전의 경우인 3을 그대로 가져와 저장한다.

하지만, 0이 오면 앞의 1,2는 고정적으로 0과 함께해야한다.

그래서 결국 아래와 같다.

즉, 현재 수가 0이고, 전의 수가 1,2라면 위와 같이

전전의 경우의 수를 가져와 전과 현재에 저장해야한다는 것이다.

Java

for (int i = 1; i <= n; i++) {
            if (input.charAt(i) == '0' && (input.charAt(i - 1) != '1' && input.charAt(i - 1) != '2')) {
                dp[n] = 0; 
                break;
            } else if (input.charAt(i) == '0' && (input.charAt(i - 1) == '1' || input.charAt(i - 1) == '2')) {
                dp[i] = dp[i - 2] % 1000000; //현재 수가 0이고 전이 1,2라면 경우의 수가 1개뿐임.
                dp[i-1] = dp[i];
            } else if (input.charAt(i - 1) == '1') {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
            } else if (input.charAt(i - 1) == '2') {
                if (input.charAt(i) <= '6') {
                    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
                } else {
                    dp[i] = dp[i - 1] % 1000000;
                }
            } else {
                dp[i] = dp[i - 1] % 1000000;
            }
        }

그렇다면 왜 dp[i] = dp[i-1] + dp[i-2] 라는 식이 성립할까?

예시를 보고 생각해보자.

색으로 나타낸 것과 같이

두가지 경우의 수로 나뉠 수 있는 부분인 2511을 만드는 과정을 본다면

25의 경우인 2,5 / 25 에 11 을 붙이는 경우,

251의 경우인 2,5,1 / 25,1 에 1 을 붙이는 경우로 나뉘게 된다.

따라서 dp[i] = dp[i-1]+dp[i-2] 라는 식이 성립하는 것이다.