[BOJ] 백준 2579 계단 오르기 (Swift)

문제

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

2579번: 계단 오르기

풀이

계단은 한번에 1칸 혹은 2칸씩 오를 수 있습니다.
다만 세칸을 연속해서 밟을 수는 없습니다.

첫번째 계단만 있는 경우 점수의 최대값은 첫번째 계단을 밟는 것 입니다.
두번째 계단만 있는 경우 점수의 최대값은 첫번째와 두번째 계단을 밟는 것 입니다. 계단의 점수는 자연수이므로, 둘 다 밟는 것이 점수가 무조건 높습니다.

세번째 계단이 있는 경우는

1. 첫번째를 밟고, 세번째를 밟는 경우
2. 두번째를 밟고, 세번째를 밟는 경우

네번째 계단이 있는 경우는,

1. 첫번째 계단까지 밟았을 때의 최대값 + 두번째 계단의 점수 + 네번째 점수
2. 두번째 계단까지 밟았을 때의 최대값 + 네번째 계단 점수

3번 연속으로는 밟을 수 없으니
지금 계단보다 3칸 전의 계단까지 밟아온 최대 값에서, 직전 계단을 밟고 지금 계단을 밟는 경우와
지금보다 2칸 전의 계단까지 밟아온 최대 값에서, 지금 계단을 밟는 경우 중
더 큰 값이 n번째 계단을 밟았을 때의 총 점수의 최대 값일 것입니다.

정의 : $f(n)$ = n번째 계단을 밟았을 때, 총 점수의 최대 값
초기값 : $f(1) = array(1), f(2) = array(1) + array(2)$
점화식 : $f(n) = max(f(n - 3) + array(n - 1), f(n - 2)) + array(n)$

소스코드

후기

dp는 점화식만 떠올리면 풀 수 있는데 점화식 떠올리는 것이 항상 어려웠습니다..
n번째 계단까지 있을 때, 무조건 n번째 계단을 밟아야하고, 최대 점수를 어떻게 구할지 떠올리면서 점화식을 구했습니다.