[python] 2579. 계단 오르기

문제: https://www.acmicpc.net/problem/2579

 

풀이

오늘 문제는 경우의 수를 나누어 풀어야 하는 문제로, 점화식을 찾는데 어려움이 있었습니다.

i를 점수 계산으로, j를 0/1/2번 연속 밟을 때로 간주하여 문제를 해결했습니다.

 

따라서, dp[i][j]는 i번 계단을 j번 연속 밟았을 때의 최대점수를 의미합니다.

 

그림을 보면서 설명드리겠습니다.

 

dp[0]일 때, j = 0, 1, 2는 초기값 0입니다. 

 

dp[1]일 때, j = 0은 계단을 밟지 않은 경우로 초기값 0입니다. 

dp[1]일 때, j = 1은 계단을 1번 밟은 경우로 10 입니다.

dp[1]일 때, j = 2는 계단을 연속 2번 밟은 경우이지만 첫번째 계단이기 때문에 2번 밟을 수 없고, 10 입니다. 

 

dp[2]일 때, j = 0은 계단을 밟지 않은 경우입니다.

두 번 연속 계단을 밟지 않는 경우는 없기 때문에, 1번 밟거나 2번 밟은 값 중에 큰 값을 가져옵니다. (max 값)

dp[2]일 때, j = 1은 계단을 1번 밟은 경우입니다.

이전 계단을 밟지 않아야지만 지금 밟은 계단이 1번 밟은 계단이 되기 때문에, dp[1][0]의 값을 가져오게 됩니다.

dp[2]일 때, j = 2은 계단을 연속 2번 밟은 경우입니다.

이전 계단을 밟아야지 지금 밟은 계단이 연속 2번 밟은 계단이 되기 때문에, dp[1][1]의 값을 가져오게 됩니다.

 

이런 식으로 쭉 2차원 배열을 채워주고,

정답은 마지막 계단을 반드시 밟아야 하기 때문에 

dp[n][1], dp[n][2] 중의 최댓값인 max(dp[n][1], dp[n][2])이 정답이 됩니다 ! 

 

 

 

 

 

 

n = int(input())
score = []
for _ in range(n):
    s = int(input())
    score.append(s)

dp = [[0]*3 for _ in range(n+1)]

for i in range(1, n+1):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = dp[i-1][0] + score[i-1]
    dp[i][2] = dp[i-1][1] + score[i-1]

print(max(dp[n][1], dp[n][2]))