[백준/C++] 2579번 계단 오르기 (DP 문제)

백준 2579번 계단 오르기

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

 

이번 계단 오르기 문제는 2차 배열을 이용해 풀었다.

전에 풀었던 DP 문제에서 세번째 연속되면 안되는 조건이 추가되어, 그 조건을 컨트롤하는데 추가 배열이 필요했다. (D[300][3]으로 설정해줘도 됨.)

 

d[i][1] -> 전 계단을 건너뛰고 밟은 i 번째 계단

d[i][2] -> 전 계단을 밟고 두번 연속되게 밟은 i 번째 계단

(d[i][2]일 때는 무조건 d[i-1][1]을 밟았다고 해야됨 & 다음 계단은 무조건 건너뛰어야됨) 

이라는 조건이 붙는다. 

 

여기서 내가 간과한 점:

d[i][1] = max(d[i - 2][1], d[i - 2][2]) + vec[i];

당연히 d[i-2][2] 가 d[i-2][1]보다 더 클 것이라 생각한 점이다.

맨 앞에 2,3 같은 몇 개의 경우는 그렇지만, 뒤로 갈 수록 연속될 때 획득하는 점수가 달라지기 때문에 d[i-2][1]가 클 때도 있다는 것이다. 따라서 위 처럼 경우를 나눠줘야한다. 

#include<iostream>
#include<vector>
using namespace std;
int d[300][300];
int main() {

	int n;
	cin >> n;
	vector<int> vec;
	int result = 0;
	vec.push_back(0);
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		vec.push_back(num);
	}
	
	d[1][1] = vec[1];
	d[1][2] = 0;
	d[2][1] = vec[2];
	d[2][2] = vec[1] + vec[2];
	for (int i = 3; i <= n; i++) {
		d[i][1] = max(d[i - 2][1], d[i - 2][2]) + vec[i];
		d[i][2] = d[i - 1][1] + vec[i];
	}
	cout << max(d[n][1], d[n][2]) << endl;
	return 0;
}