[BaekJoon][2591] 숫자카드

BAEKJOON ONLINE JUDGE

 

한국정보올림피아드 시.도 지역본선 2005

 

2591 숫자카드

 

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

 

 

 

DP

dp <- index번째 수를 마지막으로 만들 수 있는 카드의 경우의 수

 

dp[0] = 1;

dp[i] = input[i]가 0이 아니면 dp[i - 1]   -->  이전까지 배치된 카드에 새로 추가된 수(한자리) 카드를 놓으면 된다.
10 <= input[i] * 10 + input[i + 1] <= 34 이면 dp[i - 2]  --> i번째와 i + 1번째 수를 사용해서 10이상, 34이하의 카드를 만들 수 있으면 그 이전까지 만든 카드에 두 수를 합친 카드를 놓으면 된다.

 

원리는 위와 같고, bottom up 방식으로 구현을 하였고, i - 1에서 가져오는 것이 아니라 i를 i + 1, i + 2에 넣는 방식으로 구현하였다.

 

아래 코드에서 input[i]번째의 수와 매칭되는 dp index는 i + 1이다. 이는 손으로 직접 코드를 살펴보면 알 수 있을 것이다.

 

 

#include <stdio.h>
 
int dp[45];
char input[45];
 
int main()
{
    int i;
 
    scanf("%s", input);
 
    dp[0] = 1;
    for (i = 0; input[i]; i++) {
        input[i] -= '0';
        if (input[i]) {
            dp[i + 1] += dp[i];
            if (input[i] * 10 + input[i + 1] - '0' <= 34)
                dp[i + 2] += dp[i];
        }
    }
 
    printf("%d\n", dp[i]);
 
    return 0;
}
 

 

반응형