프로그래밍/알고리즘

BOJ 11057 · 오르막 수

반응형


알고리즘 분류 : 다이나믹 프로그래밍  


오르막 수를 DP로 구현하는 문제다. 오르막 수란 각 자리의 수가 오름차순을 이루는 숫자를 말한다. 0으로 시작할 수 있으며, 인접한 자리의 숫자가 같아도 오르막 수이다.


  • D[N][M] : M으로 끝나는 N자리 오르막 수
  • D[1][0] = 1, D[1][1] = 1, ‥‥ , D[1][9] = 1
  • D[N][0] = D[N-1][0] : 0으로 끝나는 N자리 오르막 수
  • D[N][1] = D[N-1][0] + D[N-1][1]
  • D[N][2] = D[N-1][0] + D[N-1][1] + D[N-1][2]
  • ‥‥
  • D[N][9] = D[N-1][0] + D[N-1][1] + ‥‥ + D[N-1][9]





C++ 소스코드


#include <cstdio>

int n, ans;
int d[1001][10];
const int mod = 10007;

void solve() {
    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] %= mod;
        }
    }
    for (int i=0; i<=9; i++) ans += d[n][i];
    printf("%d\n", ans%mod);
}

int main() {
    scanf("%d", &n);
    solve();
    return 0;
}




Python 3 소스코드


n = int(input())
d = [[0]*10 for _ in range(n+1)]
mod = 10007

def solve():
    for i in range(10):
        d[1][i] = 1
    for i in range(2, n+1):
        for j in range(10):
            for k in range(j+1):
                d[i][j] += d[i-1][k]
            d[i][j] %= mod

solve()
print(sum(d[n])%mod)




참고



반응형