알고리즘 유형 : 다이나믹 프로그래밍
풀이 없이 스스로 풀었나요? : ❌
https://www.acmicpc.net/problem/2579
솔루션
이 문제는 전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다.
앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.
일단 계단의 갯수가 2이하라면 모든 계단의 합을 출력한다.
계단의 갯수가 3개 이상이라면 3번쨰 계단까지는 수동으로 직접 계산한다.
4번째 부터는 마지막 계단을 밟기 전에 2칸으로 올라온 경우와 1칸으로 올라온 경우를 비교해서 최댓값을 계속 갱신시켜나가는 것입니다.
✨ max(dy[i - 2] + stairs[i], dy[i - 3] + stairs[i - 1] + stairs[i])을 통해 최대값을 선택하면 된다.
❔ 3번째 계단 까지 초기값을 설정해 주는 이유 ➡ 수식에 i - 3이 들어가서 인덱스 범위를 지켜주기 위해서 이다.
❔ 1칸으로 올라온 경우가 dy[i - 1]이 아닌 이유 ➡ 3칸 연속으로 올라오면 안되는 규칙으로 인해 dy[i - 3]에서 시작한다.
소스 코드
import sys
input = sys.stdin.readline
if __name__ == "__main__":
n = int(input())
stairs = [int(input()) for _ in range(n)]
dy = [0] * n
if n <= 2:
print(sum(stairs))
else:
dy[0] = stairs[0]
dy[1] = stairs[0] + stairs[1]
dy[2] = max(stairs[1] + stairs[2], stairs[0] + stairs[2])
for i in range(3, n):
dy[i] = max(dy[i - 2] + stairs[i], dy[i - 3] + stairs[i - 1] + stairs[i])
print(dy[n - 1])
후기
한 번에 점화식을 만들려고 하다 보니 점화식을 작성하는데 어려움이 있었다.
아직 다이나믹 프로그래밍에 익숙하지 않아 한 단계씩 쪼개가며 생각해 보는 연습이 필요하다고 느꼈다.
