백준 2579 풀이 (다이나믹 프로그래밍, bottom-up, 계단 오르기)

이번 문제는 매번 그렇듯이 나에게 상당히 어려웠다. 

재귀로 풀면 안된다는 느낌은 단박에 왔고, 다이나믹 프로그래밍을 써야한다는 느낌이 들었다. 물론 어떻게 써야할지 몰라서 문제였다.

그래서 다이나믹프로그래밍의 강좌를 듣고 bottom-up형식으로 풀어야한다는 것을 알게 되었다.

bottom-up이란 작은 문제부터 풀어나가면서 결과를 저장시켜서 for 구문을 사용하여 푸는 방식이다.

 

일단 계단 오르기의 규칙은 다음과 같다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

여기서 중요한 것은 연속된 세 개의 계단을 밟아서는 안된다는 것이다. 따라서 f(n)의 최댓값을 저장하기 위해서는 어떠한 과정을 거쳐서 저장할지를 고민해야한다.

25가 존재하는 계단까지의 총합을 구하기 위해서는 2가지 방법이 존재한다.

1. 20에서 2계단

2. 10에서 2계단+1계단

중요한 것은 왜 2계단을 먼저 뛰어야 하냐이다!!!

그 이유는 바로 25에서 시작한다고 할때 3계단을 연속해서 밟으면 안되기 때문에 반드시 시작은 2계단 부터 뛰어서 총합을 구한다고 전제를 두었다.

즉, 1번을 이용하여 (20까지의 최댓값 + 25)값과 2번을 이용하여 (10까지의 최댓값 + 15 + 25)값을 비교하여 최댓값을 최댓값 리스트에 누적 시키면 되는것이다. 그럼 얼추 점화식 비스므리한게 나온다.(문과라 점화식을 잘 모른다....ㅎ)

 

f(n) = stair(n) + max( f(n-2), f(n-3) + stair(n-1) )

(stair는 기존에 계단에 정해져 있는 값, f는 n까지의 최댓값)

 

따라서 이 점화식을 이용하여 이쁘게 코딩을 하면 된다.

n = int(input())

stair = [0 for i in range(301)]
for i in range(n):
    stair[i] = int(input())
total = [0 for i in range(301)]
total[0] = stair[0] 
total[1] = stair[0] + stair[1]
total[2] = stair[2] + max(stair[0], stair[1])
for i in range(3,n):
    total[i] = stair[i] + max(total[i-2], total[i-3]+stair[i-1])
print(total[n-1])