BOJ - 2579. 계단 오르기 (C++)

2579. DP

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

 

 

[풀이]

점화식을 1차원 배열로 만들면 연속해서 계단을 밟는 조건을 표현하기 어려워 2차원 배열 d로 선언한다.

또한 각 계단의 점수를 s 배열에 저장해둔다.

d[k][1]은 연속적으로 계단을 밟지 않고 올라와서 k번째 계단에 올라왔을 때 점수의 최댓값을 의미하고 

d[k][2]는 직전 계단을 밟아 두 번째 계단이며 k번째 계단일 때 점수의 최댓값을 의미한다.

따라서 d[k][1]일때는 반드시 k-2번째 계단을 밟았을 것으므로 max( d[k-2][1], d[k-2][2] ) + s[k] 가 되고

d[k][2]일때는 반드시 직전 계단인 k-1번째 계단을 밟았을 것이므로 d[k-1][1] + s[k] 가 된다.

 

#include "bits/stdc++.h"
using namespace std;

int d[1000001][3];
int s[1000001];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	for (int i=1; i<=T; i++) cin >> s[i];
	d[1][1] = s[1];
	d[2][1] = s[2];
	d[2][2] = s[1] + s[2];
	
	for (int i=3; i<=T; i++){
		d[i][1] = max(d[i-2][1], d[i-2][2]) + s[i];
		d[i][2] = d[i-1][1] + s[i];
	}
	cout << max(d[T][1], d[T][2]);
}