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

11057: 오르막 수 문제

최대한 점화식을 구하려고 생각하다보니 규칙을 발견하게 됐다! 다른 DP 문제와는 다르게 2차원 배열을 이용하여 DP를 저장해야지 풀려서 생각하는데 조금 시간이 걸린 것 같다.

dp[n][n]에서 첫번째부터 생각을 해보면

dp[1]=1  1  1  1  1  1  1  1  1  1  => 10

dp[2]=10 9  8  7  6  5  4  3  2  1 => 55

dp[3]=55 45 36 28 21 15 10 6 3 1 => 220

.

.

.

이런 식으로 나아가는데 dp[i]와 dp[i-1]간의 관계를 살펴보면 dp[i][1]=dp[i][10]이고

dp[i][2]=dp[i][1]-dp[i-1][1]

dp[i][3]=dp[i][2]-dp[i-1][2]

.

.

이런 식으로 나아간다. 따라서 이렇게 쭉 뻗어나가면 점화식을 얻을 수 있다.

사실 밑에 코드도 더 간단하게 한줄로 적을 수 있지만 이때 정신이 나간건지 똑같은 동작원리인데 코드를  어렵게 썼다.

정리하다보니 더 쉽게 푸는 방법을 알 수 있었던 듯하다!

 

그리고 10007로 나눈 나머지를 dp배열에 저장할 때마다 그 결과값을 저장해줘야한다.

이거와 관련된 모듈러 계산을 조금 더 공부해야겠다 

 

 

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


int dp[1001][11];

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