[백준]2579번 계단오르기 - dp 기초

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

2579번: 계단 오르기

 

dp라는 분야를 알고 dp기초단계를 풀면서 알고리즘의 재미를 느끼게 됨..

 

나는 다음과같이 풀었다. overlap은 연속된 계단 횟수이다.

비용 배열인 E를 E[N+1][2]로 설정해준이유는 다음과같다.

내가 N=k일때의 경우에 왔다고 하자. k일때 나는 2계단을 넘어온 경우와, 바로 이전 1계단을 넘어온 경우가 있다.

(overlap = 0 인경우와 overlap = 1 인 경우).

E[N+1] 만 지원하는 경우 overlap = 0 인경우와 overlap = 1인 경우를 같은 경우로 받아들여서, 그걸 구분하기위해 이렇게 만들었다. 

단순히 2계단 전과, 1계단 전의 경우 중 최대값을 구하는 방식으로 풀었다.

#include <iostream>
#include <vector>

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

int solve(int N, int (*E)[2], int* S, int overlap = 0){
	if (N == 0){
		//std::cout << " 0 is " << N << "\n";
		return S[0];
	}
	if (N == 1){
		//std::cout << " 1 is " << N << "\n";
		return S[1];	
	}
	if (E[N][overlap] != 0){
		//std::cout << " cache N is " << N << "\n";
		return E[N][overlap];
	}
	if (overlap == 1){
		//std::cout << " overlap N is " << N << "\n";
		E[N][overlap] = solve(N-2, E, S) + S[N];
	}else{
		//std::cout << " N is " << N << "\n";
		E[N][overlap] = max(solve(N-2, E, S) + S[N], solve(N-1, E, S, overlap + 1) + S[N]);
	}
	return E[N][overlap];
	
}
int main(void){
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL);
	int N = 0;
	
	std::cin >> N;
	int E[N+1][2] = {{0,}};
	int S[N+1] = {0,};
	
	for(int i=1; i<=N; ++i){
		std::cin >> S[i];
	}
	
	std::cout << solve(N, E, S);
	return 0;
}

 

성공!