[Python] 백준 11057 오르막수

11057번: 오르막 수 (acmicpc.net)

11057번: 오르막 수

처음 문제를 이해하고 완전이 내 것으로 만들기까지 10일이 걸렸다. 사실 10일 정도면 양호한 숫자인 듯 하다. 초반에 20일 넘겨도 다음날 되면 매번 잊어버리는 문제가 수두룩 하였으니..

참고로 나는 아이디를 2개 사용한다. 처음에 이해한 코딩을 저장용으로 쓰고, 본 아이디는 틀린문제 보기에서 집중적으로 본다. 그날 풀지 못하면 이해하고 다음날 또 푼다. 또 풀지 못하면 이해하고 다다음날 또 푼다.

 

그렇게 풀다 보니 코드가 비슷하지만 서로 다른 코드가 여러 개 생겼고, 완전히 내것으로 만든 느낌이 든다.

 

 

코드 작성 1 

# i : 길이, j = 마지막 수

dp = [[0] * 10 for i in range(1001)]
n = int(input())
for j in range(10):
    dp[1][j] = 1
for i in range(2, n + 1):    #2자리 ~ n자리까지
    for j in range(10):
        if j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(sum(dp[n]) % 10007)

 

코드 작성 2 

dp = [[0] * 10 for _ in range(1001)]
n = int(input())
for i in range(10):
    dp[1][i] = 1
for i in range(2, n+1):
    dp[i][0] = 1
    for j in range(1, 10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(sum(dp[n])%10007)

 

코드 작성 3 

dp = [[0] * 10 for _ in range(1001)]
n = int(input())
for i in range(10):
    dp[1][i] = 1
for i in range(2, 1001):
    dp[i][0] = i
    for j in range(10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(sum(dp[n])%10007)

 

코드 작성 4 

n = int(input())
dp = [1]*10
for i in range(1,n) :
    for j in range(1,10) :
        dp[j] += dp[j-1]

print(sum(dp)%10007)

 

코드  풀이

우선 n이 1일 경우에는 0,1,2,3,4,5,6,7,8,9 이렇게 10개가 된다.

그리고 끝자리가 0일 경우 n이 증가해도 1개밖에 올 수 없다. 0, 00,000,0000,00000

 

그리고 점화식은 dp[i] = dp[i-1][j] + dp[i][j-1]가 성립된다.