[11057] 오르막 수 - C++

---

문제

왜 DP를 써야 하는지 감조차 오지 않을 당신을 난 이미 알고 있다.

 

기본 적으로 입력이 1일 때는 10개이다.

0 1 2 3 4 5 6 7 8 9

2일 때

00 01... 09 - 10개
11 12... 19 - 9개
22 23... 29 - 8개
33 34... 39 - 7개
...
99 - 1개

3일 때

000 001... 009 - 10개
011 012... 019 - 9개
022 023... 029 - 8개
...
999

뭔가가 보인다면 대단한 것이며, 안 보여도 좋다, 당신의 눈을 뜨이게 하는 것이 나의 역할이다.

 

Q. DP 테이블에 어떻게 의미를 부여해 줘야 할까?

A. DP [i] = i번째 숫자가 처음인 상태에서의 최대 경우의 수

 

위의 설명은 좀 어려울 수 있으니 그림으로 보자

 

그림 설명

처음(n = 1)은 자기 자신밖에 없으니 최대 경우의 수가 1일 수밖에 없다.

처음 상태

 n = 2일 때는 말이 달라진다

01, 02... 09

' 10 '은 불가능하기 때문에 0에서 시작하는 화살표가 사라진 것을 볼 수 있다.

이 것이 문제를 해결할 키(key)이다.

 

n = 2, 1부터 시작할 때

코드

#include <bits/stdc++.h>
#define mod 10007

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
unsigned long long dp[11];

int main(){
  init();
  cin >> n;
  for(int i = 0; i < 10; ++i) dp[i] = 1;

  for(int i = 1; i < n; ++i)
    for(int j = 0; j <= 9; ++j)
      dp[j] = accumulate(dp + j, end(dp), 0) % mod;

  cout << accumulate(dp, end(dp), 0) %mod;

  return 0;
}

---

글을 마치며

이틀 전에 풀었던 문제를 글을 쓰기 위해 다시 풀어보았는데 쉽지 않았다.

풀었다고 자만하지 말고, 굽히고 굽히며 배우자.