DP - 2591 숫자카드

문제 설명

이번 문제는 가능한 카드배열의 수를 구하는 문제로,

• 1 ~ 34까지의 숫자를 가진 카드들로 배열을 구성.
• 최대 40자 이하의 숫자로 이뤄짐

이 되어야 합니다.

접근법 (DP)

1. 각 Index에 따라서 조건
   • 한자리 : 1~9인 지 파악
   • 두자리 : 10 ~ 34인 지 파악
2. 조건에 맞다면 이전의 경우의 수를 +
3. 모든 조건을 계산 후, 가장 마지막 DP Data를 return

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        
        for(int i = 1; i < len + 1; i++) {
            char c = str.charAt(i - 1);
            if(c != '0') {
                dp[i] += dp[i - 1];
            }
            
            if(i >= 2) {
                int num = 
                    Integer.parseInt(str.substring(i - 2, i));
                
                if(10 <= num && num <= 34) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        
        System.out.println(dp[len]);
    }
}

느낀 점

• DP는 확실히 문제유형이 DP라는 걸 파악하는 게 중요하다고 생각이 들었음.