문제

문제 링크

어떻게 접근할 것인가

  • 이 문제은 디피로 접근할 수 있는 문제이다.
  • 각 자리에 들어올 수 있는 0 ~ 9까지의 숫자의 개수를 저장해놓는다.
  • 0은 다음자리로 1 밖에 못보내고 9는 다음자리로 8밖에 못보낸다는 사실을 이용하면 깔끔하게 풀리는 문제이다.

코드

#include <cstdio>

long long n, num[101][10];
int main(){
    for(int i = 1; i < 10; i++)num[1][i] = 1;
    scanf("%lld", &n);    
    for(int i = 1; i < n; i++){
        num[i+1][0] = num[i][1] % 1000000000;
        for(int j = 1; j < 9; j++) num[i+1][j] = (num[i][j-1] + num[i][j+1]) % 1000000000;
        num[i+1][9] = num[i][8] % 1000000000;
    }
    long long ans = 0;
    for(int i = 0; i < 10; i++) ans = (ans + num[n][i]) % 1000000000; 
    printf("%lld", ans);
}

느낀점

  • 이지