[C/C++] 백준 #2591 숫자카드(동적계획법)

일반적으로 경우의 수를 판단할 때에는 많이 사용되는 알고리즘 기법이 동적계획법(Dynamic Programming)입니다.

 

number cards

 

이 문제는 1부터 34까지의 숫자 중 일부를 나열했을 때 나온 결과를 보고서 어떤 카드가 사용될 수 있는지 알아보는 방법입니다.

카드가 개수가 한정되어 있다면, 동적계획법을 사용할 때 보다 복잡하겠지만, 여기서는 카드의 개수가 한정되어 있지 않으니 계산하기가 편하죠.  단지 숫자 범위가 34라는 것만 문제가 될 뿐입니다.

 

문제의 링크는 다음과 같습니다.

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

2591번: 숫자카드

 

숫자 0에 대해서 예외처리하는 것이 좀 필요한 것 빼고는 큰 문제가 없습니다.  예를 들어서 101 이라는 숫자를 얻었다면, 10, 1 이라는 종류 한가지만 얻어야 한다는 것이죠.

 

제가 사용한 방법입니다.  일단 2개의 초기값은 다음과 같이 정했습니다.

\[ d_0 = 1, d_1 = 1 \]

 

다음으로는 조건에 따라서 다른데, 현재 숫자와 이전숫자와의 조합이 10이상 34이하인 경우에는 전전항을 더하고, 현재 숫자가 0이 아니면 1을 더하도록 했습니다.

 

프로그램은 조건문을 쓰지 않고, 조건식을 곱하는 형태로 조건문을 대신했습니다.

제가 작성한 소스입니다.

//----------------------------------------------------------------------------------------
//    baekjoon #2591
//        - by Aubrey Choi
//        - created at 2019-08-20
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    char line[44];
    int dp[41], i;
    scanf("%s", line);
    dp[0]=1; dp[1]=(line[0]>'0');
    for(i=2;line[i-1];i++)
    {
        int t = (line[i-2]-'0')*10+line[i-1]-'0';
        dp[i] = dp[i-1]*(line[i-1]>'0')+dp[i-2]*(t>=10 && t<=34);
    }
    printf("%d\n", dp[i-1]);
}