글 읽기 - 이 점화식으로 풀면 왜 안될까요?

wwaa456 5년 전 0

쉬운 계단 수(10844) 문제와 같은 방식으로 점화식을 세워서 풀어봤는데요

N 자리 수의 숫자 마지막 자리에 오는 숫자를 L 이라고 가정했을 때,

N-1 번 째 자리에 올수 있는 숫자는 L 과 L-1 입니다 (L이 0인 경우는 모든 숫자가 0인 경우만 가능하기 때문에 경우의 수가 1 이라고 생각했습니다)

이때 모든 d[n][0] = 1 이고,

d[n][l] = d[n-1][l-1] + d[n-1][l]

이라고 점화식을 세워 풀어봤는데, 답이 틀리다고 나오네요

하지만 논리상 어디가 틀린건지 잘 모르겠어서 조언을 구합니다

감사합니다

n = int(input())
d = [0] + [[1]*10] + [list(range(1,11))]
# index0 : 사용안함
# index1 : n(자리수)가 1이면 경우의 수도 각 1가지
# index2 : 2 자리수인 경우의 수

if n >= 3:
    d += [[1]*1 + [0]*9 for i in range(n-2)]
    # index 3 ~ n 까지 l이 1인 경우 경우의 수 1로, 나머지는 0으로 초기화

    for i in range(3, n+1):
        for j in range(1, 10):
            d[i][j] = d[i-1][j-1] + d[i-1][j]
            # 점화식 d[n][l] = d[n-1][l-1] + d[n-1]

print(sum(d[n]) % 10007)

evenharder 5년 전 1

N 자리수의 마지막 자릿수가 L이라고 할 때, N-1번째 자릿수는 0에서 L까지 올 수 있기 때문입니다.

wwaa456 5년 전 1

아아..

계단수 문제를 풀고와서 그랬는지

완전 논리 오류에 빠져있었군요

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 점화식으로 풀면 왜 안될까요?

wwaa456 5년 전 0

evenharder 5년 전 1

wwaa456 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말