DP > 쉬운 계단 수 (10844번)

문제

---

풀이

 

자자 중요한건 뭐다?

코테는 큰 수를 다루니까 왠만하면 자료형은 long long으로 쓰고!! 출력을 lld로 하고!!!

나머지 구하는 거면 저장할 때랑 출력할 때마다 나눠서 저장하고 출력해!

그리고 증감연산자 쓸거면 변수 선언하고 초기화 꼭꼭하고 임마!!

 

이것도 바로 전에 풀었던 문제랑 같은 맥락이야

계단 수니까 맨 뒤에 수가 어떤게 올지 고민하면 돼!

그럼 2차원 배열로 맨 뒤의 수가 뭐가 될지 정해주면 되는거지

이제 DP의 중요한 부분인 점화식을 고려해보자

2차원이니까 d[i][j]고, 이건 길이가 i이면서 맨 뒤 숫자가 j가 오는 계단수의 갯수를 저장하는 배열인거지

그럼 얘는 계단수니까 d[i-1][j-1]이랑 d[i-1][j+1]의 경우가 더해지는 경우겠지?

이 떄 중요한게 있어

바로 맨뒤에서 2번쨰 숫자가 0이랑 9일때야

우선 j가 0일때는 i-1이 -1이니까 탈락, 9일떄는 j+1이 10이니까 탈락이야

즉 뭐다?

j-1>=0 일떄만 d[i-1][j-1]이 되고, j+1<=9 일떄만 d[i-1][j+1]이 되는거지

그래서 이 조건 걸어서 더해줘야돼!

그럼 아래 코드 봅시당

---

코드

#include <iostream>
#include <stdio.h>
#define MAX 101
#define mod 1000000000

long long d[MAX][10];

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    long long res=0;
    cin >> n;
    
    d[1][0]=0;
    for(int i=1;i<=9;i++)
    {
        d[1][i]=1;
    }
    
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=9;j++)
        {
            d[i][j]=0;
            if(j+1<=9) d[i][j]+=d[i-1][j+1];
            if(j-1>=0) d[i][j]+=d[i-1][j-1];
            d[i][j]%=mod;
        }
    }
    
    for(int i=0;i<=9;i++) res+=d[n][i];
    printf("%lld\n",res%mod);
    
    return 0;
}