숫자카드.md

DONE_DATE	2025/02/06

숫자카드

난이도

• 골드 5

문제

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

알고리즘 분류

• 다이나믹 프로그래밍

회고

• 역시 DP 문제는 코드가 예쁘다
• 일종의 조합을 구하는 문제인데 초기에 재귀로 풀었다가 메모이제이션을 이용한 DP로 바꿔서 풀었다.

전체코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> memo; // 메모이제이션 테이블

int dp(const vector<int>& v, int start) {
    int n = v.size();
    if (start == n) { // 숫자를 모두 사용했을 때
        return 1;
    }

    if (memo.count(start)) { // 메모이제이션 확인
        return memo[start];
    }

    int count = 0;

    // 1자리 카드 시도
    if (start < n) {
        int one_digit = v[start];
        if (one_digit >= 1 && one_digit <= 9) {
            count += dp(v, start + 1);
        }
    }

    // 2자리 카드 시도
    if (start < n - 1) {
        int two_digit = v[start] * 10 + v[start + 1];
        if (two_digit >= 10 && two_digit <= 34) {
            count += dp(v, start + 2);
        }
    }

    memo[start] = count; // 결과 메모이제이션
    return count;
}

int main() {
    string input;
    cin >> input;

    vector<int> arr;
    for (char c : input) {
        arr.push_back(c - '0');
    }

    memo.clear(); // 메모이제이션 테이블 초기화
    cout << dp(arr, 0) << endl;

    return 0;
}