백준 2579번 계단 오르기

계단 오르기 성공 풀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	16659	6265	4662	38.207%

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 

6
10
20
15
25
10
20

예제 출력 

75

힌트

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 초등부 4번

알고리즘 분류

• 다이나믹 프로그래밍

이 문제는 전형적인 다이나믹 프로그래밍 문제이다. 처음에는 이 문제를 깊이우선 탐색으로 해보려고 했으나, 그전 계단 그전전계단을 방문했는지 체크하는게 조금 까다로워서 디피로 풀어볼 생각을 해봤다.

문제 제약 조건 중에 현재 계단과 바로 전 계단은 밟을수 있지만 전전계단,전계단을 밟고나서 현재 계단을 밟을수는 없다는 조건이 있다.

이 제약조건을 고려 해야 하기때문에 dp를 2차원 배열로 잡아야 한다.

dp[i][j] -> i번째 계단에서 바로전 계단이 j번 밟힌 경우

예를 하나들면 dp[4][1] -> 4번째 계단만 밟음

dp[4][2] -> 4번째 계단과 3번재 계단을 밟음

이런식으로 dp 배열을 잡았다.

그렇게 하고 나서 

dp[1][1], dp[2][1], dp[2][2] 까지는 그냥 인풋값을 넣어줬고 반복을 3부터 n까지 돌렸다.

1. dp[i][1] = max(dp[i - 2][1],dp[i - 2][2]) + input[i];
2. dp[i][2] = input[i] + input[i - 1] + max(dp[i - 3][1] ,dp[i - 3][2]);

핵심 코드는 위와 같다.

즉 현재 계단 1개만을 밟은경우

전계단은 밟지 못하므로 전전계단에서 나올수있는 점수중 최대값 +

현재 계단의 점수를 더해주게 되면 현재 계단만을 밟았을때 총 최대 점수를 구할수 있게된다.

그 다음 경우는

현재 계단과 바로전 계단 2개의 계단을 밟은 경우이다.

이런 경우에는 2개의 계단을 밟았으므로 현재 계단의 전전계단을 밟았다면 연속으로 3개를 밟게 되므로 불가능하다. 

그렇기 때문에 전전전계단에서 나올수있는 점수의 최대값과 현재계단의 점수를 더해준것이 이 경우에서의 최대값이다.

머리속으로 그림을 그려보면 이해가 될것이다.

그렇게 어려운 문제는 아닌것 같다.

전체코드

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int input[301];
int dp[301][3];
 
 
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
 
	dp[2][1] = input[2];
	dp[2][2] = input[1] + input[2];
	dp[1][1] = input[1];
	for (int i = 3; i <= n; i++)
	{
		dp[i][1] = max(dp[i - 2][1],dp[i - 2][2]) + input[i];
		dp[i][2] = input[i] + input[i - 1] + max(dp[i - 3][1] ,dp[i - 3][2]);
	}
 
	cout << max(dp[n][1], dp[n][2]) << endl;
 
    return 0;
}