[백준/C++] 10844번_쉬운 계단 수

문제는 다음과 같습니다.

일단 이 문제 푸는데 삼일? 걸렸던 것 같다.
계속 분명히 맞는데 왜 틀렸지? 이랬는데, 알고보니 마지막 답으로 써서 낸 자료형이 달라서..
실환가 long long인데 계속 int로 반환해서 .. 드디어 계속 틀렸던 이유 찾았다.
나름 꼼꼼하다고 생각했는데 아니었나보다.

아무튼 이제 dp문제가 재밌기 시작하는 경지에 다다른것 같다.
이 계단수 문제도 재미있다.

먼저, 이차원 배열 dp[i][j]를 이용하였는데,
이 의미는 다음과 같다.

dp[i][j] = i번째 자리수가 j로 끝났을 때 만들 수 있는 계단 수

예를 들어, dp[2][4] 는 두 번째 자리가 4로 끝났을 때 만들 수 있는 계단 수 이다.
가능한 경우는 34, 54로 dp[2][4]=2가지가 된다.

그리고 이 dp[i][j]를 구할 때 예외만 잘 처리하면 된다.

• 자리가 0으로 끝날 때: 이웃할 수 있는 수는 1밖에 없다.
• 자리가 9로 끝날 때: 이웃할 수 있는 수는 0밖에 없다.
• 나머지 경우(i로 끝날 때): 이우살 수 있는 수는 i-1, i+1로 두 가지이다.

이에 해당하는 코드는 다음과 같다.

if(j==0) dp[i][j]+=dp[i-1][1];
else if(j==9) dp[i][j]+=dp[i-1][8];
else{ // j가 1~8일때
  dp[i][j]+=(dp[i-1][j-1]+dp[i-1][j+1]);
}

그리고 전체 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long dp[102][10]={0, };
    long long mod=1000000000;
    int n; cin>>n;

    for(int i=1; i<=9; i++) dp[1][i]=1;

    for(int i=2; i<=n; i++){
      for(int j=0; j<=9; j++){
        if(j==0) dp[i][j]+=dp[i-1][1];
        else if(j==9) dp[i][j]+=dp[i-1][8];
        else{ // j가 1~8일때
          dp[i][j]+=(dp[i-1][j-1]+dp[i-1][j+1]);
        }
          dp[i][j]%=mod;
      }
    }

    long long res=0;
    for(int i=0; i<=9; i++) res+=dp[n][i];
    cout<<res%mod<<"\n";

    return 0;
}