[백준] No.2579 - 계단 오르기 (C++)

문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

풀이

다이나믹 프로그래밍 문제이므로 일단 직관적인 top-down 방식으로 풀어보았다.

 

메모이제이션을 위한 배열 max_stair[300][2] 선언하는데 2차원으로 선언하는 이유는 해당 위치가 직전 계단과 연속되는지를 저장하기 위해서이다. 

 

max_stair[ ][ 0 ] 에는 두 계단을 뛰어 연속되는 계단이 없는 경우를, max_stair[ ][ 1 ] 에는 한 계단만 올라가 이전의 계단과 연속되는 경우를 저장한다.

 

이후 현재의 계단 위치 stair_idx에서 연속되는 계단 수인 succession가 1인 경우에만 한 계단만 오를 수 있도록 ascendStair(stair_idx+1, succession+1)를 재귀호출을 해준다.

 

두 계단을 올라가는 경우는 계단의 개수를 초과하지 않는 경우 ascendStair(stair_idx+2, 1)를 재귀 호출해준다.

 

해당 재귀 호출 값들을 max_stair에 저장하여 다이나믹 프로그래밍을 구현한다.

 

 

코드

	#include <iostream>
	#include<string.h>
	using namespace std;
	int stair_num;
	int stair_scores[300];
	int max_stair[300][2];
	int ascendStair(int stair_idx,int succession){
	if(stair_idx == stair_num-1)
	return stair_scores[stair_num-1];
	int& ret = max_stair[stair_idx][succession];
	if(ret != -1)
	return ret;
	int max = 0;
	int temp;
	if(succession !=2){ //3개 이상이 연속으로 선택됨을 방지
	temp = ascendStair(stair_idx+1, succession+1) + stair_scores[stair_idx];
	max = max> temp ? max: temp;
	}
	if(stair_idx < stair_num -2){
	temp = ascendStair(stair_idx+2, 1)+ stair_scores[stair_idx];
	max = max> temp ? max: temp;
	}
	ret = max;
	return ret;
	}
	int main() {
	cin>>stair_num;
	for(int i=0; i<stair_num ; ++i)
	cin>>stair_scores[i];
	memset(max_stair, -1, sizeof(max_stair));
	int max =0;
	int temp;
	temp = ascendStair(0, 1);
	max = max> temp ? max: temp;
	temp = ascendStair(1, 1);
	max = max> temp ? max: temp;
	cout<<max<<'\n';
	return 0;
	}

view raw [BaekJoon]_1149_RGB거리.cpp hosted with ❤ by GitHub

 

bottom-up 방식

모든 재귀 호출은 for문으로 구현이 가능하다. 해당 문제를 buttom-up방식으로 구현해보자.

계단은 3칸 이상을 연속으로 오를 수 없기 때문에 N번째 계단으로 오르는 경우는 단 두 가지뿐이다.

 

첫 번째는 직전의 칸(N-1)에서 한 칸만 올라와 N번째에 도달한 경우이다.

이 경우는 N-1과 N이 연속되었으므로 N-1로 도달할 때는 반드시 두 칸을 올라왔어야 한다. 즉, N-3에서 두 칸을 올라온 경우다. 따라서 N-3의 메모이제이션 저장 값을 사용한다.

 

두 번째는 두 칸을 올라와 N-2에서 N으로 도달한 경우이다.

이 경우는 N-2의 메모이제이션 저장 값을 사용하면 된다.

 

이를 점화식으로 나타내면 아래와 같다.

1. dp[N] = stair_scores[N-1] + stair_scores[N]+dp[N-3] ;

2. dp[N] = stair_scores[N] + dp[N-2] ;

 

이를 stair_num-1 까지 순회하여 dp[stair_num-1]에 저장되어 있는 값이 답이다.

 

#include <iostream>
using namespace std;
 
int stair_num;
int stair_scores[300];
int dp[300];
 
int main() { 
  cin>>stair_num;
 
  for(int i=0; i<stair_num ; ++i)
    cin>>stair_scores[i];
 
  dp[0] = stair_scores[0];
  dp[1] = stair_scores[1]+stair_scores[0];
  dp[2] = max(stair_scores[0], stair_scores[1] ) +stair_scores[2];
 
  for(int i=3; i<stair_num ; ++i)
    dp[i] = max(stair_scores[i-1]+stair_scores[i] + dp[i-3],stair_scores[i] +dp[i-2]);
  
  cout<<dp[stair_num-1]<<'\n';
  return 0;
}