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

2579번: 계단 오르기

 

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

 

 

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

 

 

풀이과정

문제에서 요구하는 사항은 아래와 같다.

1. 계단은 한번에 1개 혹은 2개
2. 연속으로 세개의 계단은 불가능
3. 마지막 도착 계단은 반드시 밟아야한다

위와 같은 조건들 3가지를 지키고 마지막 계단에서 얻을 수 있는 점수의 최대값을 출력하면 되는 형식에 문제였었다.

해당 문제의 풀이를 진행하면서 어떻게 접근을 해야할까 고민을 하다가 문득 의문점이 들었다.

dp는 크게 2가지 방법으로 문제를 풀 수 있다고 생각한다.

1. 과거의 값으로 현재의 값을 구성하는 방식.
   "dp[i] = dp[i - 2] + list[i]" 처럼 i의 값을 구하기 위해서 이전의 값들을 가져오는 방식. 
   
2. 현재의 값으로 미래를 구성하는 방식.
   "dp[i + 2] = dp[i] + list[i + 2]" 처럼 i + 2의 값을 구하기위해 현재의 값으로 미래의 값을 지정해주는 방식.

위와 같은 방식으로 접근할 수 있다고 생각을 하는데 1번의 방법이나 2번의 방법이나 모두 코드가 진행이 되다보면

같은 결과값을 도출해 내기때문에 두가지 방법 모두를 사용해서 풀 수 있지않을까? 라는 생각이 문득 들었다.

그래서 2번의 방법을 사용해서 문제의 접근을 해보았다.

 

#include <iostream>
#include <algorithm>

// 계단은 한번에 1개 혹은 2개
// 연속으로 세개의 계단은 불가능
// 마지막 도착 계단은 반드시 밟아야한다.
int		main(void)
{
	int n;
	int	dp[303] = {0}, stairs[303] = {0}, counts[303] = {0};

	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> stairs[i];
	for (int i = 0; i <= n; i++) {
		if (dp[i] == 0) dp[i] = stairs[i];
		if (i + 2 < n + 1) {
			dp[i + 2] = dp[i] + stairs[i + 2];
			counts[i + 2] = 1;
		}
		if (i + 1 < n + 1 && counts[i] + 1 < 3) {
			if (i + counts[i] + 1 < n || i + 1 == n) {
				if (dp[i + 1] < dp[i] + stairs[i + 1]) {
					dp[i + 1] = dp[i] + stairs[i + 1];
					counts[i + 1] = counts[i] + 1;
				}
			}
		}
	}

	std::cout << dp[n];

	return (0);
}

그것의 풀이를 진행했던 코드가 위와 같다.

counts라는 배열로 몇번연속으로 한칸으로 왔는지 확인하고, 3번 연속으로 한칸을 갈 경우를 미리 방지해버린다.

위의 코드를 바탕으로 예제를 진행할 경우에는 옳은 출력값이 나오는것을 확인할 수 있었는데 정작 제출을 해보니

2번 풀이방식의 결과

라는 값이 나오는 것을 확인 할 수 있었다. 그래서 무엇이 문제인가를 찾아보니 아래와 같은 반례를 찾을 수 있었다.

3
40
50
60

answer = 110

위에 예제의 경우에는 2번째 계단을 가고 1칸을 뛰어 3번째 계단에 도달해서 110이라는 결과값을 내야만하지만

위와 같은 코드의 경우에는 값의 대소를 비교해서 counts의 값과 상관없이 큰값이 우선적으로 적히기때문에
최종적으로 110이라는 결과값에 도달할 수 없었다.

( 3번 조건을 바탕으로 사전에 미리 저지를 해도 다른 예제에서 틀려버리는 일이 생겼었다. )

 

위에서 틀린 내용으로 생각을 해보니 1번 풀이 방식 (과거의 값으로 현재의 값을 구성하는 방식.) 으로 진행을 했으면 과거의 값을 기준으로 현재의 값을 구성하다보니 조금 더 반례를 신경 안쓰고 코드 풀이가 가능할 거 같은데
2번 풀이 방식 (현재의 값으로 미래를 구성하는 방식.)을 사용하다보니 신경써야하는 반례가 너무 많아졌었다.

그래서 결론적으로는 계단오르기 같이 "연속으로 세개의 계단은 불가능" 식의 조건이 걸려있는 dp 문제의 경우에는
1번 풀이 방식을 사용하는 것이 훨씬 코드가 간단하고 편해진다는 사실을 확인 할 수 있었다.

 

 

1번 풀이 방식의 해석은 다음과 같다.

모든 마지막 계단까지 도달하는 방법은

1. 계단은 한번에 1개 혹은 2개
2. 연속으로 세개의 계단은 불가능
3. 마지막 도착 계단은 반드시 밟아야한다

 이라는 조건으로 인해 n번까지 계단에 도달하는 방법은

2가지 방법으로만 도달이 가능하다. 그 이외의 방법들은 규칙의 어긋나는 도착 방법이므로 가능하지않다.

그래서 위의 방법을 점화식으로 정리를 해보자면

1번째

dp[n] = stairs[i] + stairs[i - 1] + dp[i - 3]

2번째

dp[n] = stairs[i] + dp[i - 2]

이렇게 2개로 나누어지게 된다. 그래서 위의 조건들을 바탕으로 도달하는 방법자체가 정해져있으니 계단을 몇번밟아가면서 왔는지를

생각하지않고 문제 풀이가 가능해지게된다.

code

#include <iostream>
#include <algorithm>

// 계단은 한번에 1개 혹은 2개
// 연속으로 세개의 계단은 불가능
// 마지막 도착 계단은 반드시 밟아야한다.
int		main(void)
{
	int n;
	int	dp[303] = {0}, stairs[303] = {0};

	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> stairs[i];
	dp[1] = stairs[1];
	dp[2] = stairs[1] + stairs[2];
	dp[3] = std::max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
	for (int i = 3; i <= n; i++) {
		dp[i] = std::max(stairs[i] + dp[i - 2], stairs[i] + stairs[i-1] + dp[i-3]);
	}
	for (int i = 1; i <= n; i++) {
		std::cout << dp[i] << " ";
	}
	std::cout << dp[n];

	return (0);
}

 

후기

dp 문제를 보고 어떻게 접근을 해야할지 확실하게 알게 되는 문제였던 거 같다.

덕분에 많이 배우고 성장했다.