[백준] 2579번 계단 오르기

단계별로 풀어보기 동적 계획법 1의 7단계 문제이다.

2579번: 계단 오르기

오랜만에 C++로 풀었는데 벡터가 아니라 동적할당을 이용해서 입력을 받았다.

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

int main() {
	int n;
	cin >> n;
	int* stair = new int[n];
	int** score = new int*[n];
	for (int i = 0; i < n; i++) {
		score[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> stair[i];
	}
	if (n > 0) {
		score[0][0] = stair[0];
		score[0][1] = stair[0];
	}
	if (n > 1) {
		score[1][0] = stair[0] + stair[1];
		score[1][1] = stair[1];
	}
	if (n > 2) {
		score[2][0] = stair[1] + stair[2];
		score[2][1] = stair[0] + stair[2];
	}

	for (int i = 3; i < n; i++) {
		score[i][0] = max(score[i - 3][1] + stair[i - 1] + stair[i], score[i - 3][0] + stair[i - 1] + stair[i]);
		score[i][1] = max(score[i - 3][1] + stair[i - 2] + stair[i], score[i - 2][1] + stair[i]);
	}
	cout << max(score[n - 1][0], score[n - 1][1]) << endl;
	return 0;
}

stair 배열에는 입력으로 들어온 각 계단의 점수를 저장하고 score 배열에는 현재 그 칸까지 올라왔을 때 최대로 얻을 수 있는 점수를 저장했다.

score는 이차원배열인데 score[i][0]에는 i-1번째 계단을 밟고 i번째 계단까지 올라왔을 때의 얻을 수 있는 최대 점수이고 score[i][1]에는 i-1번째 계단을 밟지 않고 i번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수를 저장했다. 

 

동적할당으로 이차원배열을 선언할 때에는 이렇게 하면 된다.

int** score = new int*[n];
for (int i = 0; i < n; i++) {
	score[i] = new int[2];
}