<2579> 계단 오르기 - DP

실버 III

 

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

 

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

 

 

풀이

import sys

n = int(sys.stdin.readline().rstrip())
point = [int(sys.stdin.readline().rstrip()) for i in range(n)]
point.insert(0, 0)
dp = [0] * (n+1)


if n == 1:
    print(point[1])

elif n == 2:
    print(point[1]+point[2])

else:
    dp[1] = point[1]
    dp[2] = point[1] + point[2]
    for i in range(3, n+1):
        dp[i] = max(dp[i-3]+point[i-1]+point[i], dp[i-2]+point[i])

    print(dp[n])

 

내가 어려웠던 점

 

1. 시작을 첫번째 계단에서 할 수도 있고, 두번째 계단에서 할 수도 있는데, 이걸 어떻게 구분할지. 

처음에 dp for문을 돌렸는데, 그럼 이걸 첫계단에서 시작하는 경우랑, 두번째 계단에서 시작하는 경우를 나누어서 for문을 다시 돌려야 하는지에 대해 고민.

첫번째에서 시작 / 두번째에서 시작을 고민할 필요가 없는게, 시점을 바꿔야함. 

어디서 "시작" 하냐로 보지말고, 어디서 "끝"나냐를 생각해야함 .

내가 여기서 끝나는데, 그러면 여기로 오려면 최댓값이 바로 전 계단에서 왔냐, 전전 계단에서 왔냐에 대한 최댓값 비교만 해주면 되는 것.. 

 

n = 1과 n = 2는 정해져 있으니,

n = 3부터 dp[1]과 dp[2]의 경우의 수를 계산해서 최댓값을 넣어 놓으면 , n이 더 큰 숫자가 되더라도 결국은 그것이 최댓값을 향하는 길임. 

 

 

2. 여러 조건이 있는데, 이 조건을 다 일일이 구현하려고 함.

예를 들어 세 계단 연속으로 못밟는 것이든가..(flag를 만들어 또 if문으로 제어하려고 함)

그걸 제어해서 조건에 맞지 않는 dp값을 없애려고 하는 것이 아니라, 

애초에 조건에 들어 맞는 dp 값 두가지 정도, 혹은 경우의 수만큼을 생각해서, 그 경우의 max나 min을 판단해야 함

 

=> dp 문제 특성상 앞에서부터 최대/최소 판단을 하면, 그 조건이 자동으로 만족 되는 경우가 많음

그러니까 dp 로 판단 되는 문제면, if로 조건 걸려고 하지 말고 점화식을 빨리 찾는것이 답이 될 것 같다