[BOJ] 11057번 오르막수 / 사용언어 : 파이썬(python)

※ 문제링크

11057번: 오르막 수

해당 문제는 동적프로그래밍과 관련된 문제로 단순 반복문으로도 답을 구할 수 있지만 메모리와 속도를 문제의 조건에 맞게 하기 위해서는 메모이제이션을 활용해야하는 문제였다. 모든 동적프로그래밍의 문제가 그렇듯 점화식이 존재한다고 가정하고, n = 1부터 4까지의 값들을 보며 규칙을 찾아보았다. 확인결과 발견한 규칙은 아래와 같다.

 

0__	1__	2__	3__	4__	5__	6__	7__	8__	9__
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1
220	165	120	84	56	35	20	10	4	1

각각의 수를 보면 n = 2일때부터 각각의 첫번째 열의 값은 그 이전 값들의 합이되고, 그 다음 값은 그 이전 행의 열의 값으로 해당 행의이전 열의 값을 빼준것과 같은 것을 알 수 있다. 즉, dp를 길이가 10인 다수의 리스트로 이루졌다고 하면, dp[i][k] = dp[i[k-1] - dp[i-1][k-1]인 것을 알 수 있다. 해당 점화식을 찾아낸 후에 구현하는 것은 그리 어렵지 않았다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 N을 정수로 변환해준다.

2. N을 바탕으로 dp를 만들어주고 결과값을 반환해줄 함수를 작성한 후 입력값을 넣어 결과값을 구한 후 출력한다.

 

N = int(input())

def find(N):
    dp = [[1 for _ in range(10)]]
    for i in range(N-1):
        dp.append([0 for _ in range(10)])

    for i in range(1, N):
        for k in range(10):
            if k == 0:
                dp[i][k] = sum(dp[i-1])
            else:
                dp[i][k] = dp[i][k-1] - dp[i-1][k-1]
    ans = sum(dp[N-1]) % 10007
    print(dp)
    return ans

print(find(N))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.