2579번: 계단 오르기(백준 C++)

 

www.acmicpc.net/problem/2579

2579번: 계단 오르기

코드

#include <iostream>
using namespace std;

int score[300] = {0, };
int stair[300] = {0, };
int n;

int max(int a, int b){
	return a > b ? a : b;
}

void init(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> stair[i];
	}
}

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

int main() {
	init();
	solve();
	return 0;
}

 

문제 풀이

DP 문제입니다. 점화식을 찾으면 바로 풀 수 있는 종류이죠.

DP 문제는 대개 주어진 상황에서 최대 혹은 최소값을 찾도록 요구합니다.

그리고 그런 문제의 해결법은 보통 다 비슷하죠

 

N번째의 최대(소)값을 구하기 위해서는 

이전까지의 최대(소) 값 + N번째의 값 찾기 입니다.

다만, 문제에 따라서 이 이전까지의 최대(소)값을 구하는 방식이 달라집니다. 그럼 이 문제는 어떨까요?

1. 계단은 한번에 한 칸이나 두 칸을 올라갈 수 있다.

2. 연속된 세 개의 계단을 모두 밟을 수는 없다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

그렇다면 도착점(N)을 기준으로 생각할 수 있는 점화식이 있네요.

점화식 1. (N-2)까지의 최대값 + N의 값

N이 6이므로 4번째 계단까지의 최대값 + 6번째 계단의 값을 더하는 방법입니다.

 

점화식 2. (N-3)까지의 최대값 + (N-1)의 값 + N의 값

한 번에 세 개의 계단을 모두 올라갈 수없기 때문에

N-3계단부터 시작해서 2칸 1칸의 방법으로 도달하는 방법입니다.

 

즉 도달하는 방법(점화식)이 두 가지이므로 이제 매 계단마다 두 점화식 중 큰 값을 가져오면서

마지막 계단까지 진행해주면 정답이 나오겠습니다.

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

 

저 같은 경우에는 계단 각 층의 점수는 stair 배열에 저장하고, 각층에서의 최대값은 score 배열에 저장했습니다.

score[n] 의 경우에는 N+1층에서의 최대점수가 되겠습니다.