백준 2591번 숫자카드 :: 마이구미

이 글은 백준 알고리즘 문제 2591번 "숫자카드" 를 풀이한다.

정올 출제 문제로써, 풀이 방법은 동적계획법을 통해 해결한다.

문제 링크 - https://www.acmicpc.net/problem/2591

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.

나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.

카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오.

문제는 입력되는 수를 표현할 수 있는 경우의 수를 구해야한다.

다음과 같이 입력되는 수 273을 첫번째 수부터 차례대로 나타내보자.

2

위 상황에서 2를 추가하면, 다음과 같은 경우를 구할 수 있다.

2 7
27

3을 추가하면, 위의 각 경우에서 3을 넣어 표현할 수 있는 경우를 보자.

2 7 3
2 73
27 3

위처럼 차례대로 추가하면서, 일의 자리와 십의 자리만 확인하면서 탐색하는 방법이 가능하다.

이러한 경우, DFS 와 같이 모든 경우를 접근할 수 있다.

코드로 표현하면 다음과 같다.

public static void dfs(String s, int v, int idx) {
    if (s.equals(input)) {
        ++ans;
    }

    for (int i = 1; i <= 2; i++) {
        if (input.length() < idx + i) {
            break;
        }
        String card = input.substring(idx, idx + i);
        int n = Integer.parseInt(card);
        card = String.valueOf(n);

        if (1 <= n && n <= 34) {
            dfs(s + card, n, idx + i);
        }
    }
}

하지만 이러한 경우 시간복잡도는 O(2^N) 가 되기 때문에, 시간 초과가 발생한다.

결국 다른 접근이 필요하다.

하지만 위 방법을 이해했다면, 크게 다를 게 없다.

입력된 수를 차례대로 그림으로 표현한다면, 다음과 같다.

위 그림을 통해 규칙을 찾을 수 있다.

마지막 수가 십의 자리라면, 하나의 수가 추가된 후의 경우의 수는 변함없다.

예를 들어, 27에서 1을 추가해도 표현할 수 있는 경우의 수는 증가되지 않는다.

위 그림처럼 단순히 27인 카드에서 1 카드가 추가된 것이기 때문이다.

그렇다면, 27 1 에서 2를 추가해보자.

27 1 2
27 12

마지막 수가 일의 자리라면, 단순히 일의 자리를 추가하는 경우와 마지막 수와 추가되는 수를 합쳐서 십의 자리를 추가할 수 있는 경우가 있다.

그 결과 위처럼 분리될 수 있다.

이것을 활용해서 동적계획법을 위한 점화식을 만들 수 있다.

DP[N][L] = N번째 수에서 마지막 수가 L 일 때의 경우의 수 {L = 1(일의 자리), 2(십의 자리)}

그 과정에서 카드의 값은 1 ~ 34 라는 것을 인지해야한다.

또한 0 에 대한 상황을 고려해야한다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2005/2591.java

private void solve() {
    // dp[N][L] - L자리 수면서 N번째 수까지의 가능한 배열 갯수 L => 일의 자리, 십의 자리
    // 카드로 표현할 수 있는 수는 일의 자리와 십의 자리 밖에 존재하지 않음.
    char[] array = sc.readLine().toCharArray();
    int len = array.length;
    int[][] dp = new int[41][3];
    int prev = (array[0] - '0') * 10;
    dp[1][1] = 1;
 
    for (int i = 2; i <= len; i++) {
        int v = array[i - 1] - '0';
        if (v == 0) {
            if (prev + v <= 34) {
                dp[i][2] = dp[i - 1][1];  
            }
            continue;
        }
 
        if (prev + v <= 34) {
            dp[i][1] = dp[i - 1][2] + dp[i - 1][1];
            dp[i][2] = dp[i - 1][1];
        } else {
            // 34보다 큰 수라면 십의 자리가 될 수 없다.
            dp[i][1] = dp[i - 1][1] + dp[i - 1][2];
        }
        prev = v * 10;
    }
    System.out.println(dp[len][1] + dp[len][2]);
}