백준 2591번 숫자카드

코드 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static String str = "";
	static int count = 0;
	static int N1;
	static int N2;
	static int len;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();
		len = str.length();
		dfs(0);
		System.out.println(count);
	}
	public static void dfs(int index) {
		if(index==len) {
			count++;
			return;
		}
		N1 = str.charAt(index)-'0';
		N2 = 0;
		if(index<len-1) {
			N2 = (str.charAt(index)-'0')*10+str.charAt(index+1)-'0';
		}
		//N1, N2 0일때도 있음
		if(N1==0) {
			return;
		}
		if(N2>34) {
			dfs(index+1);
		}
		else if(N2==0){
			dfs(index+1);
		}
		else {
			dfs(index+1);
			dfs(index+2);
		}
		
	}
}

풀이방법

👉우선 처음 문제를 딱 봤을때 생각난 풀이는 백트래킹 방식이었다.

1. 입력값으로 들어온 문자열을
   N1에는 한자리수로 끊고, N2에는 두자리수로 끊었다.
   카드가 0일경우는 없으므로 N1==0일때 return하는 코드는 사실 없어도 무방하다.
2. N2 > 34 일때는 두자리수로 끊을 수 없다는 뜻이므로, 다음 인덱스탐색으로 넘어간다.
3. N2가 0일때, 즉 01, 02이런 경우의 수 인데, 이런 카드는 없으므로, 그냥 다음 인덱스 탐색으로 넘어간다.
4. N2가 0도 아니고 N2<=34라면, 한자리 카드, 두자리 카드 두 경우의 수가 모두 가능하므로, 탐색을 두번해준다.
5. 마지막 숫자까지 탐색에 성공하면 경우의 수를 하나 증가시킨다.

🔉이코드도 통과가 되긴하지만, 시간이 오래걸린다.

코드 2

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

public class NumCard {
    static String str = "";
    static int N1;
    static int N2;
    static int len;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        len = str.length();
        int[] dp = new int[len+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= len; i++) {
            N1 = str.charAt(i-1)-'0';
            N2 = (str.charAt(i-2)-'0')*10+str.charAt(i-1)-'0';
            if(N1==0&&N2<=34){
                dp[i] = dp[i-2];
                continue;
            }
            if(str.charAt(i-2)-'0'==0||N2>34){
                dp[i] = dp[i-1];
            }
            else {
                dp[i] = dp[i-1]+dp[i-2];
            }
        }


        System.out.println(dp[len]);
    }

}

풀이방법

👉dp방법으로 푸는 풀이

1. 문제의 주어진 입력값은 이렇게 6개의 경우의 수가 존재한다.
   2 7 1 2 3
   2 7 1 23
   2 7 12 3
   27 1 2 3
   27 12 3
   27 1 23

2. 만약 다음에 숫자가 하나 추가되고, 뒤에 숫자 2개가 34보다 크다면,
   즉, 2 7 1 2 3 5 라면, 새로 생기는 두자리 카드의 경우의 수는 없으므로, 이전 27123의 경우의 수와 동일하다
   2 7 1 2 3 5
   2 7 1 23 5
   2 7 12 3 5
   27 1 2 3 5
   27 12 3 5
   27 1 23 5

3. 하지만, 뒤에 숫자 2개가 34보다 작다면, 즉,271232라면,
   2 7 1 2 3 2
   2 7 1 23 2
   2 7 12 3 2
   27 1 2 3 2
   27 12 3 2
   27 1 23 2
   이전 경우의 수와 더불어 새로 생기는 두자리 카드인 32도 가능하게된다.
   2 7 1 2 32
   2 7 12 32
   27 1 2 32
   27 12 32
   📢여기서 포인트는 32를 빼고 본다면, 2712의 경우의 수에 32를 붙인것과 동일한 모습을 보인다.

이를 dp로 정리하자면 현재 dp값은 dp[i-1]+dp[i-2]가 되는것이다.
이런식으로 dp를 적절히 34를 기준으로 분기해서 점화식을 세우면 된다.

📢이때 주의해야할 점이 0이 나올때다.

1. 현재 탐색하는 숫자가 0 즉 ...10, ...20, ...30 이런식일때,
   10, 20, 30은 34에 포함 되므로
   2 7 1 2 10
   2 7 1 2 20
   2 7 1 2 30
   이런식으로 dp[i] = dp[i-2]와 동일한것을 볼 수 있다.

2. 현재 탐색하는 이전 숫자가 0 즉 ...01,...02, ...03일때는,
   01,02,03이란 카드는 없으므로 1,2,3 한자리수 카드만 쓰는 방법 밖에는 없다.
   2 7 1 2 10 1
   2 7 1 2 20 2
   2 7 1 2 30 3
   따라서 이전dp 값과 동일한 dp[i] = dp[i-1]이 된다.

후기

dp의 점화식을 분기에 따라 세워야 하는 방법이었다.
분기로 나누는거에 더해서 0처리를 따로하는 반례가 있었기에 해당 조건도 고려해야해서 까다로운 문제인것 같다.