[BaekJoon] 2591 숫자카드 (Java)

1.  문제 링크

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

2.  문제

요약

• 1부터 34까지 수가 적힌 카드가 충분히 많이 있습니다.
• 카드들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적습니다.
• 카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 그것을 가지고 거꾸로 카드의 배열을 찾으려고 합니다.
• 가능한 카드의 배열이 모두 몇 개인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 40자 이하의 숫자로 이루어진 카드의 숫자를 차례로 적어 놓은 것이 주어집니다.
• 출력: 첫 번째 줄에 가능한 카드 배열이 몇 개인지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getCaseNum(char[] input) {
		int[][] dp = new int[41][2];
		int prev_num = (input[0] - '0') * 10;
		dp[1][0] = 1;
		for(int i = 2; i <= input.length; i++) {
			int n = input[i - 1] - '0';
			if(n == 0) {
				if(prev_num + n <= 34) {
					dp[i][1] = dp[i - 1][0];
				}
				continue;
			}
			if(prev_num + n <= 34) {
				dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
				dp[i][1] = dp[i - 1][0];
			} else {
				dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			}
			prev_num = n * 10;
		}
		return dp[input.length][0] + dp[input.length][1];
	}	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		char[] input = br.readLine().toCharArray();
		br.close();
		Main m = new Main();
		bw.write(m.getCaseNum(input) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 2차원 행렬 dp를 생성하는데 행의 길이는 주어진 숫자의 최대 길이가 40이므로 41로 만들고, 열의 길이는 각 위치까지의 마지막 숫자가 일의 자리일 경우와 십의 자리일 경우를 나눠야하므로 2로 만듭니다.
• 만약 추가되는 수가 0이라면, 카드에 1부터 34까지만 존재하기 때문에 하나의 숫자로서 추가하지 못하므로 마지막 수에 추가되는 수를 붙여 하나의 숫자로 만듭니다. 이 때, 만약 만든 숫자가 34를 넘는다면 해당 숫자는 만들 수 없는 것이므로 해당 경우는 제외합니다.
• 만약 마지막 숫자가 십의 자리라면, 뒤에 하나의 숫자가 추가되었을 때 십의 자리 뒤에 새로 들어온 숫자를 붙여 하나의 숫자를 만들기 때문에 이전까지의 경우의 수와 다르지 않습니다.
• 만약 마지막 숫자가 일의 자리라면, 뒤에 하나의 숫자가 추가되었을 때 해당 숫자를 일의 자리로 숫자 하나를 추가하는 경우와 마지막 숫자에 들어온 숫자를 합쳐 하나의 숫자로 만드는 경우로 나뉘어질 수 있습니다.
• dp 배열에서 열의 index가 0인 경우가 마지막 숫자가 일의 자리인 경우, index가 1인 경우가 마지막 숫자가 십의 자리인 경우를 의미한다고 한다면 아래와 같은 점화식을 생성할 수 있습니다.
  • dp[i][0] = dp[i - 1][1] + dp[i - 1][0]
  • dp[i][1] = dp[i - 1][0]
• 만약 추가하려는 수가 마지막 수와 합쳐져 하나의 숫자를 만들었을 때 34보다 크다면 해당 경우는 합쳐서 하나의 숫자를 만들 수 없기 때문에 일의 자리로 하나의 숫자를 추가하는 경우만 생각합니다.