[백준 c++] 2579 계단 오르기 (실3)

📌 서론

이 문제는 내가 알고리즘 스터디를 열심히 했을 때 풀었던 문제다

간단하면서도 동적할당의 개념을 잘 얻을 수 있는 좋은 문제!

 

이 문제는 사실 동적 계획 이외에 재귀 함수를 사용해서 풀 수도 있지만 그렇게 푼다면

시간 초과 문제로 맞을 수 없었다.

 

🙅🏻‍♂️ 틀린 답안

#include <iostream>
using namespace std;

int N;
int MAX;
int* stair;
int result;

void function(int idx, int nextCnt) {
	
	if (idx == N - 1 ) {
		if (nextCnt == 2) return;
		if (MAX < result + stair[idx]) MAX = result + stair[idx] ;
	}
	else if(nextCnt != 2){
		result += stair[idx];
		if (nextCnt != 2) 	//1칸위로 올라가고 싶은데 먼저 확인
			function(idx + 1, nextCnt + 1);
		if (idx + 2 < N) 
			function(idx + 2, 0);
		result -= stair[idx];
	}

}

int main() {

	cin >> N; if (N < 1 || N > 300) return 0 ;
	stair = new int[N];
	for (int i = 0; i < N; i++) cin >> stair[i];
	MAX = 0; result = 0;

	function(0,0);
	function(1,0);

	cout << MAX << endl;

	return 0;
}

재귀를 사용한 코드이다.

모든 가능성을 다 탐색한 후 가장 최대값이 나오는 경우를 찾는 방법인데 이렇게 하면 아래와 같이 시간초과 결과로

문제를 풀 수 없다.

 

 

동적 계획법 ( 다이나믹 프로그래밍 ) 에 대해서 알아야 문제의 해답을 찾을 수 있다.

✨동적계획법 관련 글 참고 https://greedy-blow-you-away12.tistory.com/8

 

💻 정답 코드

#include <cstdio>
using namespace std;
int max(int a, int b) { return a > b ? a : b; }
int main () {
    int n, i;
    int arr[300];
    int dp[300];
    scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &arr[i]);
    dp[0] = arr[0];
    dp[1] = max(arr[0]+arr[1], arr[1]);
    dp[2] = max(arr[0]+arr[2], arr[1]+arr[2]);
    for (i = 3; i < n; i++) dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]);
    printf("%d\n", dp[n-1]);
    return 0;
}

 

 

⏱ 결과