[백준] 2591번. 숫자 카드(JAVA)

문제

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

---

풀이(35분)

import java.io.*;

public class Main {

    static String num;
    static int count = 0;
    static int[] dp;
    static final int MAX_NUM = 34;

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

        num = br.readLine();

        dp = new int[num.length()];

        if(num.charAt(num.length() - 1) == '0'){ // 마지막 자리가 0인 경우
            dp[0] = 0; // 마지막 자리로만 만들 수 있는 숫자 없음
        }else{
            dp[0] = 1; // 마지막 자리로만 만들 수 있는 숫자 1개 존재
        }
        if(num.length() > 1){ // 길이가 2 이상인 경우
            String substring = num.substring(num.length() - 2, num.length()); // 2자리 문자 파싱
            if(substring.charAt(0) == '0'){ // 2자리의 앞글자가 0이라면
                dp[1] = 0; // 그 자리는 0으로 초기화
            }// 2자리 문자이고, maxNum보다 작으며, 첫 번째 자리가 0이 아닌 경우
            else if(Integer.parseInt(substring) <= MAX_NUM && substring.charAt(1) != '0'){
                dp[1] = 2;
            }
            else{
                dp[1] = 1;
            }
        }

        // 123 이면 3번째의 경우 0~2까지 봐야함. 즉 섭스트링(0,2)
        for(int i = 2; i < num.length(); i++){
            String substring = num.substring(num.length() - (i+1), num.length() - (i-1));
            if(substring.charAt(0) == '0'){ // 파싱한 첫번째 자리가 0인 경우 0
                dp[i] = 0;
                continue;
            }
            dp[i] = dp[i-1]; // 바로 전의 자리로 만들 수 있는 경우의 수 + 자기 자신 한 장
            if(Integer.parseInt(substring) <= MAX_NUM){ // 앞의 두자리가 maxNum보다 작다면
                dp[i] += dp[i-2]; // 두 개를 합쳐서 만들 수 있기에 -2번째 자리까지 생각
            }
        }
        System.out.println(dp[num.length() - 1]);
    }
}

---

문제 풀이 전략

 

문제를 꼼꼼히 읽고 경우를 나누자.

이 문제의 경우 1~34까지의 숫자 카드를 이용하여 숫자를 분할해 가는 문제이다. 여기서 중요한 조건들을 정확히 파악하자.

• 숫자의 길이는 최대 40이다.
  • 이 경우 long으로도 받을 수 없기에 String으로 입력을 받아 처리해야 한다.
• 숫자 카드는 1~34까지만 존재한다.
  • 0이 들어가는 경우 반드시 10, 20, 30의 카드에서 나온 것이다.

나의 경우 2번째 조건을 제대로 파악하지 못해서 고생을 좀 했다.

분기를 정확히 하자.

dp의 초기 조건을 설정하는 것부터 살펴보자.

여기서 dp[i]가 의미하는 것은 i+1번째 자리까지 만들 수 있는 경우의 수이다.

• dp[0]은 숫자의 첫 번째 자리에 대한 것이다.
  • 만약 0이라면, dp[0] = 0이 되어야 한다.
    • 즉, 숫자 카드를 이용해 첫 번째 자리를 만드는 경우의 수는 0이다.
  • 만약 값이 있다면, dp[1] = 1이 되어야 한다.
    • 어떤 숫자 카드든 첫번째 자리를 만들 수 있다.
• dp[1]은 숫자의 두 번째 자리까지에 대한 것이다.
  • 만약 0이라면, dp[1] = 0이 되어야 한다.
    • 이 부분이 중요한데, 숫자열을 잘랐을 때 01 같은 수를 만들 수 없다고 생각하는 것이다.
  • 만약 1~9까지의 숫자라면
    • 첫번째 자리가 0인 경우 dp[1] = 1이 되어야 한다.
      • 첫 번째 자리가 0인 경우 반드시 10, 20, 30만 되기 때문이다.
    • 첫 번째 자리가 0이 아닌 경우 dp[1] = 2이다.
      • 15를 예로 들면 1 + 5와 15가 가능하다.

이 정도 살펴봤으면 dp의 초기 설정을 감을 잡았을 것이다.

또한 dp의 진행이 어떻게 이루어질지도 느낌이 올 것이다. 한번 살펴보자.

for(int i = 2; i < num.length(); i++){
    String substring = num.substring(num.length() - (i+1), num.length() - (i-1));
    if(substring.charAt(0) == '0'){ // 파싱한 첫번째 자리가 0인 경우 0
        dp[i] = 0;
        continue;
    }
    dp[i] = dp[i-1]; // 바로 전의 자리로 만들 수 있는 경우의 수 + 자기 자신 한 장
    if(Integer.parseInt(substring) <= MAX_NUM){ // 앞의 두자리가 maxNum보다 작다면
        dp[i] += dp[i-2]; // 두 개를 합쳐서 만들 수 있기에 -2번째 자리까지 생각
    }
}

일단 현재 인덱스에 맞게 2글자를 자른다.

코드의 주석을 통해 substring의 인덱스를 정확히 이해하자.

123의 경우 1(3번째 자리)에 대해 볼 것이면 substring(0,2)가 되어야 한다. 그렇기에 num.length() = 3인 점을 이용하여 계산한 것이다.

• 만약 파싱한 첫 번째 자리가 0인 경우 dp[i] = 0이다.
  • 이 전의 초기 설정에서 살펴본 것처럼 01234 같은 숫자는 만들 수 없다고 판단하자.
• 만약 파싱한 첫 번째 자리가 0이 아니라면
  • 반드시 자기 자신 + dp[i-1]의 경우를 만들 수 있다.
  • 앞의 두 글자를 자른 것이 MAX_NUM보다 작거나 같다면
    • dp[i-2]의 값을 추가해 준다.

다시 한번 정리하자면 0이 너무나도 중요한 dp 문제였다. 꼭 문제를 잘 읽고 조건을 분기시키자.