백준 10844 풀이 (쉬운 계단수, 다이나믹 프로그래밍)

이번에는 쉬운 계단수를 풀어본다. 역시 노래를 안들으면서 풀었더니 어찌저찌 풀렸다. 앞으로 알고리즘 풀때 노래 안들어야겠다.....

 

일단 문제를 보면 별게 없다. 처음 시작부터 계단을 하나씩만 오고갈 수 있고 이렇게 나올 수 있는 경로의 총 합을 구하면된다.

그럼 대강 계단이 어떻게 경로가 생성되는지 구해본다.

f(n) = f(n-1) + f(n+1) 단, n > 0

그림을 그려보면 이전에 사용된 N값을 이용하여 다음 N+1의 계단에 총 수를 알 수 있다.(0에서 값이 조금 다르듯이, 9에서도 값이 다르기 때문에 이 부분을 염두해 두고 코딩해야한다.)

따라서 수의 길이에 따른 시작 계단별 수를 저장하기 위해 2차원 배열을 선언하고 차곡차곡 쌓아가면서 다음 수에서의 계단별 수를 저장하면 된다. 

마지막에는 구하고자 했던 N값에 해당 되는 값에서 0으로 시작하는 경우만을 빼고 합을 구해주면 수의 길이에 따른 경우의 수를 구할 수 있다.

 

0과 1의 경우는 직관적으로 알 수 있는 부분이기 때문에 직접 하드코딩으로 값을 선정해주었다. 

n = int(input())
tmp = [[0 for i in range(10)] for i in range(101)]
tmp[1] = [0,1,1,1,1,1,1,1,1,1]
tmp[2] = [1,2,2,2,2,2,2,2,2,1]
def calc(n):
    for i in range(0,10):
        if i == 0:
            tmp[n][i] = tmp[n-1][i+1]
        elif i == 9:
            tmp[n][i] = tmp[n-1][i-1]
        else:
            tmp[n][i] = tmp[n-1][i-1] + tmp[n-1][i+1]

for i in range(3,n+1):
    calc(i)
print(sum(tmp[n][1:])% 1000000000)

굳이 따지자면 이번에 구한 것은 다이나믹 프로그래밍중 bottom-up 형태의 방식이라고 할 수 있겠다. 일단 재귀함수를 사용하지 않았고, 단순히 loop구문만을 이용했기 때문.