[BOJ] 백준 2579. 계단 오르기

▶문제설명

[BOJ] 백준 2579. 계단 오르기

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

▶Hint

---

DP 문제이다.

[주어진 계단 오르기 규칙]

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

연속해서 세 개의 계단을 밟을 수 없다. 따라서 하나의 계단 기준으로 두 가지 경우로 나눌 수 있다.

1. 이전 계단을 밟은 경우

: A = dp[N-3] + stairs[N-1] + stairs[N];

[N-3]	[N-2]	[N-1]	[N]
출발 지점		여기를 밟고	여기로 도착

2. 이전 계단을 밟지 않은 경우

: B = dp[N-2] + stairs[N];

[N-2]	[N-1]	[N]
출발 지점		바로 여기로 도착

이 두 가지 경우를 비교해서 더 큰 경우를 dp테이블에 저장하면 각 위치에서 취할 수 있는 최대값을 구할 수 있다.

: dp[N] = max(A, B);

[초기 값]

dp[0] = 0;

dp[1] = stairs[1];

dp[2] = stairs[1] + stairs[2];

위와 같이 초기값을 설정하고 3번째 계단부터 식을 이용해 값을 구하면 된다.

▶Solution