2579번 계단오르기

문제링크 : www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

---

<알고리즘>

1) 각 칸에서 이동가능한 칸들의 합에서 제일 큰 값을 넣는 배열 dq생성

 

2) 0번째, 1번째, 2번째는 이 후의 점화식과는 다른 경우의 수이기 때문에 따로 설정

   2-1) 0번째 칸까지 고려한 경우, 최대 dq값은 0번째 계단 값

   2-2) 1번째 칸까지 고려한 경우, 최대 dq값은 1번째 계단값 or (0번째 계단값+1번째 계단값) 중 큰 값

   2-3) 2번째 칸까지 고려한 경우, 최대 dq값은 (0번째 + 2번째 계단값) or (1번째 계단값+2번째 계단값) 중 큰 값

 

 3) 3번째 칸 부터는 2가지 경우를 고려해, 이 둘 중 더 큰 값을 dq값으로 한다.

   3-1) 이전 상황에서 두 칸 이동한 경우, dq[i-2]+i번째 계단 값이 될 것이고

         (dq[i-2]는 i-2번째 칸으로 올때까지 가장 큰 계단 값 합)

    3-2) 이전 상황에서 한 칸 이동한 경우, dq[i-3] + i-1번째 계단 값 + i번째 계단 값이 될 것이다.

         (dq[i-1]을 더하면 그 칸에 오기 직전에 한 칸을 이동했지 두 칸을 이동했는지 모르기에

          아예 그 전 활동 값에서 한 칸+현재 칸을 더한 것임)

 

 4) 마지막 칸은 반드시 밟아야 한다고 했으므로 dq[N-1]의 값을 확인하면 N-1번째 칸에 오기까지 가장 큰 계단의 합을 알 수 있음

 

 

 

 

 

메모리 : 2016KB   시간 : 0ms

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	cin >> N;

	int stair[302] = { 0, };
	int A = 0;
	for (int i = 0; i < N; i++) {
		cin >> A;
		stair[i] = A;
	}

	int dq[302] = { 0, };
	dq[0] = stair[0];
	dq[1] = max(stair[1], stair[0] + stair[1]);
	dq[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
	for (int i = 3; i < N; i++) {
		dq[i] = max(dq[i - 2] + stair[i], dq[i - 3] + stair[i - 1] + stair[i]);
	}
	cout << dq[N - 1];
	return 0;
}