[알고리즘] 동적 계획법(Dynamic Programming) - 백준 2579번 계단 오르기

import sys
n = int(sys.stdin.readline().rstrip())
stairs = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

if n == 1:
    print(stairs[0])
elif n == 2:
    print(stairs[0] + stairs[1])
elif n == 3:
    print(max(stairs[0] + stairs[2], stairs[1] + stairs[2]))
else:
    upStair = [0 for _ in range(n)]
    upStair[0] = stairs[0]
    upStair[1] = stairs[0] + stairs[1]
    upStair[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

    for i in range(3, n):
        upStair[i] = max(stairs[i] + upStair[i-2], stairs[i] + upStair[i-3] + stairs[i-1])

    print(upStair[n-1])

풀이과정

1. stairs 배열에 계단 점수를 넣는다.
2. 계단이 1칸일 때는 1칸을 밟으면 최댓값이 된다.
3. 계단이 2칸일 때는 2칸 모두 밟으면 최댓값이 된다.
4. 계단이 3칸일 때는 1번째 + 3번째 or 2번째 + 3번째를 밟으면 최댓값이 된다.
5. 계단이 4칸 이상일 때는 마지막 도착 계단은 반드시 밟아야 한다 라는 조건을 적용해야한다. for문을 반복할 때, 마지막 칸은 stairs[i]이다.

• 만약 마지막 칸과 그 전 칸을 밟았다면, 그 전전 칸은 밟을 수 없다. 따라서 전전전 칸까지 더한 stairs[i] + upStair[i-3] + stairs[i-1] 이다.
• 만약 마지막 칸과 그 전전 칸을 밟았다면, 그 전전칸 까지 더한 stairs[i] + upStair[i-2]가 답이다.
• 두 조건 중 더 큰 값을 upStair 배열에 넣어준다.

다른 사람 풀이

import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N+3)]
arr = [0 for _ in range(N+3)]
for k in range(1,N+1):
    arr[k] = int(input())


dp [1] = arr[1]
dp [2] = arr[1] + arr[2]
dp [3] = max(arr[1] + arr[3] ,arr[2] + arr[3])


for i in range(4, N+1):
    dp[i] = max( dp[i-3] + arr[i-1] + arr[i] ,  dp[i-2] + arr[i] ) 
print(dp[N])

내가 푼 풀이의 문제는 n=1, n=2, n=3 일 경우, index를 벗어나는 오류가 발생했다. 따라서 조건을 걸어 각 경우에 대해 답을 출력했다.

별로 좋지 않은 코드인 것 같다.
다른 사람의 풀이를 참고하니, arr의 3번째 인자까지 0을 넣어주고 시작한다. 그럼 분기를 나누지 않아도 정답을 구할 수 있다!