[백준/C++] 2579 계단 오르기 (S3)

유형	난이도	완료일	링크	특이사항
DP	실버3	23/02/20	https://www.acmicpc.net/problem/2579

 

 

오답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[300];
int MAX = 0;
int sum;

void Recursion(bool jump, int idx)
{	
	if(idx<0)
		return;
	
	
	sum+=arr[idx];

	
	if(jump)
	{
		if(arr[idx-1]>arr[idx-2])
		{
			//cout <<"Add "<<arr[idx-1]<<"\\n";
			Recursion(false, idx-1);
			
		}
		else
		{
			//cout <<"Add "<<arr[idx-2]<<"\\n";
			Recursion(true,idx-2);
		}
	}
	
	else
	{		
		//cout <<"Add "<<arr[idx-1]<<"\\n";
		Recursion(true,idx-2);
	}
}

int main(void)
{
	int n; cin >> n;
	
	for(int i= 0; i< n; i++)
	{
		cin >> arr[i];
	}
		
	Recursion(true, n-1);
	cout << sum;
}

처음엔 단순히 맨 뒤의 계단부터 시작해서 앞선 계단으로 선택할 수 있는 것들 중 더 큰 것을 선택하는 재귀함수를 만들었다. 중복되는 계단 값이 연속해서 나오는 경우 등 잘못된 답이 출력 되는 경우가 많았다. 무조건 더 큰 자식(전 계단)을 선택한다고 최댓값이 나오는게 아니었다.

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[301];
int sum[2][301];

int main(void)
{
	int n; cin >> n;
	
	for(int i= 0; i< n; i++)
		cin >> arr[i];
	
	sum[0][0] = arr[0]; sum[1][0] = arr[0];
	sum[0][1] = arr[1]; sum[1][1] = arr[0]+arr[1];
	
	for(int i=2; i<n; i++)
	{
		sum[0][i] = arr[i] + max(sum[0][i-2],sum[1][i-2]);
		sum[1][i] = arr[i] + sum[0][i-1];
	}
	
	cout<<max(sum[0][n-1], sum[1][n-1]);
}

모든 계단에 대해서 해당 계단까지 오는데 밟은 계단의 최댓값을 저장해가면서 n번째 계단까지 가면 n번째 계단, 즉 마지막 계단을 밟는데 필요한 최댓값을 구할 수 있다.

문제는 계단이 3개 이상 연속되면 안되는 것인데 이는 그냥 특정 단계의 계단이 연속된 계단일 때, 연속되지 않은 계단일 때의 최대 합을 모두 저장하는 것으로 해결하였다.

n번째 계단을 밟는 방법은 n-1번째 계단에서 바로 밟는 방법과 n-2번째에서 n-1을 건너뛰고 밟는 방법으로 두 가지기 때문에 n-1을 건너뛰고 밟았을 경우, n-1을 밟고 밟았을 경우 모두를 저장해주어야 한다. 단 이때 n-1을 밟고 연속으로 n까지 밟는 경우 해당 n-1은 연속되지 않은, 즉 n-2를 밟지 않고 n-3 → n-1 → n 루트로 이어져야 한다. 따라서 n-1번째 계단의 2가지 최대 합 중 n-2을 건너뛰고 n-1을 밟은 경우의 합을 사용하면 된다.

3번 연속되지 않는다는 조건이 까다로웠던 것 같다. 전 단계의 DP문제들과 비슷해서 쉽게 풀 수 있었다.

간결한 코드

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

int dp[301];
int score[301];

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

//https://www.acmicpc.net/source/56191037

dp[i](i번째까지의 최대합)에 값을 저장할 때 애시당초 dp[i-2]와 dp[i-3]+score[i-1]중 더 큰 것을 골라 3개의 계단이 연속되는 경우가 없게 한다.

내가 ‘연속되지 않은 dp[i-1]’를 따로 저장해서 사용한 것을, 그냥 무조건 최대 값을 저장하고 dp[i-3] + score[i]로 분리해 해결한 것이다.