[백준] 11057번 : 오르막 수 with python3, cpp

03 Aug 2018

Reading time ~1 minute

풀이

D에 일단 길이가 1일 때의 값들을 저장한다.

첫루프 때는 초록색
두번째 루프때는 파란색
세번째 루프때는 주황색으로 더해지는 것이다.

  for j in range(0,10):
  D[i][j] = sum(D[i-1][:j+1])
      # -> 0은 매번 다음곳에 더해지고
      # -> 1은 두번째부터 다 더해지고

이런식으로 더해진다.

nn = int(input())
D = [[0] * 10 for _ in range(nn + 1) ]
for i in range(0,10):
    D[1][i] = 1


for i in range(2,nn+1):
    for j in range(0,10):
        D[i][j] = sum(D[i-1][:j+1])
            # -> 0은 매번 다음곳에 더해지고
            # -> 1은 두번째부터 다 더해지고

print(sum(D[nn])%10007)

#include <iostream>
using namespace std;
long long d[1001][10];
int main() {
    int n;
    cin >> n;
    for (int i=0; i<=9; i++)
        d[1][i] = 1;

    for (int i=2; i<=n; i++) {
        for (int j=0; j<=9; j++) {
            for (int k=0; k<=j; k++) {
                d[i][j] += d[i-1][k];
                d[i][j] %= 10007;
            }
        }
    }
    long long ans = 0;
    for (int i=0; i<10; i++)
        ans  += d[n][i];

    ans %= 10007;
    cout << ans << '\n';
    return 0;
}

algorithm 백준