[Java] 2011번: 암호코드 Gold 5

문제 링크

이렇게 풀어보려고 했다~..

3이상인 수를 기점으로 구획을 나눠서 가능한, 구획별로 가능한 경우의 수들을 곱하려고 했다.

생각보다 규칙을 빨리 발견한 거 같아서 코드를 뚝딱 작성해서 제출했는데,,,

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 동전 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();

        // dp
        int n = input.length;
        int[] dp = new int[n];
        dp[0] = 1;
        if (n > 1) dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 암호 처리
        int ans = 1, cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            cnt++;
            if (input[i] - '0' >= 3) {
                ans = (ans * dp[cnt - 1]) % 1000000;
                cnt = 0;
            }
        }

        // 마지막 문자 처리
        ans = (ans * dp[cnt]) % 1000000;

        // 출력
        System.out.println(ans);
    }
}

예외 케이스가 너무 많았다.

1. 27의 정답은 1인데, 2를 출력한다는 점..
2. 중간에 0이 섞이는 경우를 고려안한 점..

2번은 바로 생각이 났다.

0은 단독으로 쓰일 수도 없고, 뒤에 숫자와 결합할 수도 없고, 앞에 숫자랑만 결합이 가능하다.
그래서 누적 길이를 1 감소시키고, 기존처럼 곱하는 것이다.

20114라는 입력을 넣으면 이전에는 8이 나왔었는데, 해당 부분을 고치고 나서는 3이 잘 나온다!

그 다음 1번도 과정을 하나씩 생각을 해보니 금방 떠올릴 수 있었다.

27의 정답은 1인데, 2 7로는 사용가능하지만, 27로는 사용이 불가능하기 때문이다.

문제의 입력 예시는 25114였는데, 25와 114에서 25를 보면, 이 경우에는 2 5도 가능하고, 25도 가능하다.

즉, 7이상의 수는 앞자리 수가 2이상이면 무조건 떨어트려서 사용해야 하는 것이다.
근데 여기서 2이상이라고 했는데, 3부터는 그 전에 이미 분기된다.

그렇기에 7 이상의 수를 만났는데, 7의 앞자리 수가 2일 때만 특수한 케이스가 생기는 것이다.

예외처리를 하다보니, 생각할 게 너무 많아져서 이 방법은 그냥 포기하기로 했다~..

급할 수록 돌아가라고, 정석대로 고민해봤다,,

내가 한 건 사실 DP방식이 전혀 아니었으니,,

근데 해보니 이게 훨씬 더 간단하고 명확했다

1. 빨간색의 경우는 바로 이전 케이스에서 오는 경우이다.
   • 이 때는 i번째 수를 단독으로 사용하는 경우를 고려해서 DP[i-1]만큼의 가짓수가 생긴다.
2. 파란색의 경우는 전전 케이스에서 오는 경우이다.
   • i-1번째 수와 i번째 수를 이어 붙였을 때, 암호로 만들 수 있다면,
     즉, 26이하라면 이 케이스들도 고려가능한 것이다.
     (물론 이전 방식을 고민해봐서 알듯이, 주간에 0이 올 수도 있으니,
     엄밀히 말하면 10 ~ 26만 가능!!)
     이 부분은 숫자로 직접 변환해서 확인하면 된다!

간단히 말해
1번은 항상 고려하면 되니까, DP[i] = DP[i-1]로 초기화를 하고,
2번이 가능하면, DP[i] += DP[i-2]도 하면 된다!

그럼 코드를 짜보자!

정답

예외처리를 하지 않으면 35%에서 틀린다..

0은 무조건 앞의 숫자와 결합해야 하는데, 0으로 시작하면 결합을 할 수 없기 때문에 사용할 수가 없다 ㅎ...
그래서 문제에서도 해석할 수 없으면 0을 출력하라고 했다~
문제를 잘 읽자!!..^^...🤣

import java.io.*;

public class Main {
    static final int MOD = 1000000; // 정답이 너무 클 수 있으니까 나머지 처리

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

        // 예외처리
        if (s.charAt(0) == '0') {
            System.out.println(0);
            return;
        }

        // DP를 위한 초기값 설정
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // dp[1]을 위해 세팅 - 숫자 한 개로는 항상 생성 가능
        dp[1] = 1; // dp[i-2]를 위해 세팅

        // DP
        for (int i = 2; i <= n; i++) {
            // 1. 파란색의 경우: 숫자 하나로 표현하는 경우(항상 존제)
            int oneDigit = s.charAt(i - 1) - '0';
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] = dp[i - 1] % MOD;
            }

            // 2. 빨간색의 경우: i-1 번째 수와 i번째 수를 계산했을 떄 10 ~ 26
            int twoDigit = (s.charAt(i - 2) - '0') * 10 + oneDigit;
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] = (dp[i] + dp[i - 2]) % MOD;
            }
        }

        // 출력
        System.out.println(dp[n]);
    }
}