[C/C++] 10844: 쉬운 계단 수

10844: 쉬운 계단 수 문제

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

10844번: 쉬운 계단 수

 

뜻하지 않게 이 문제를 11057: 오르막 수를 풀고 그 다음에 바로 풀었더니 굉장히 빨리 풀었다!

오르막 수에 관한 코드 설명은 아래 링크와 같다.

https://donggul-godsang.tistory.com/66

[C/C++] 11057: 오르막 수

 

이 문제 역시 각 자리 수마다 1,2,3,..9에 대해 저장을 해야하므로  2차원 배열을 이용해야 한다.

 생각을 해보면 끝에 자리수가 1일때 그 다음 자리와의 차이가 1이라면 0 또는 2를 갈 수 있다.

마찬가지로 끝에 자리수가 2라면 1 또는 3을, 끝에 자리수가 3이라면 2 또는 4를 갈 수 있다.

이때 주의 해야할 점은 끝에 자리수가 0 또는 9라면 각각 1과 8로 밖에 갈 수 없다는 점이다.

 

그래서 DP를 이용했기 때문에 지금까지 저장한 수가 모두 인접한 자리와의 차이가 1인 것을 전제로

dp[j-1]을 통해 dp[j]를 구해보면

dp[j][0]을 구하기 위해서 dp[j-1]중에 0으로 갈 수 있는 수는 dp[j][1]밖에 없다.

마찬가지로 dp[j][9]를 구하기 위해 9로 갈 수 있는 수를 구하면 8밖에 없으므로 dp[j][9]=dp[j-1][8]이 된다.

그리고 나머지 모든 경우에 대해서는 dp[j][i]=dp[j-1][i-1]+dp[j-1][i+1];가 성립된다는 것을 알 수 있다.

그리고 dp[j][10]은 길이가 N인 계단 수가 총 몇 개 있는지 저장한다.

 

또 정답을 1,000,000,000으로 나눈 나머지를 구해야하므로 각 dp 배열 값에 1,000,000,000으로 나눈 나머지를 저장한다.

이때 dp[j][10]을 구할 때 조심해야한다, 이 수를 더할때 int형 범위를 벗어날 수 있기 때문에 더할 때마다 모듈러 계산을 해줘야한다.

dp[j][10]=(dp[j][10]+dp[j][i])%1000000000;

 

아래는 이것들을 이용한 소스코드이다!!

#include <stdio.h>
#include <string.h>


int dp[101][11];

int main(void)
  {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=9;i++)
      {
        dp[1][i]=1;
        dp[1][10]+=dp[1][i];
      }
    for(int j=2;j<=n;j++)
      {
        for(int i=0;i<=9;i++)
          {
            if(i==0)
            {
              dp[j][0]=dp[j-1][1];              
            }
            else if(i==9)
            {
              dp[j][9]=dp[j-1][8];
            }
            else
            {
              dp[j][i]=dp[j-1][i-1]+dp[j-1][i+1];
            }
            dp[j][i]%=1000000000;
            
            dp[j][10]=(dp[j][10]+dp[j][i])%1000000000;
          }
      }

    printf("%d",dp[n][10]);
  }