2579: 계단 오르기

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

2579번: 계단 오르기

설명

우선, 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 계단을 밟으면 각 계단에 쓰여있는 점수를 얻게 된다.

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

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

1. 계단은 한 번에 한 계단씩 또는 두 계단식 오를 수 있다. 즉 한 번에 두 칸이 최대! 
2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 
3. 마지막 도착 계단은 반드시 밟아야 한다.

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

결국, 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램 작성

 

핵심 아이디어

• 계단의 값을 쌓아 최댓값을 만드는 문제이기 때문에, DP 알고리즘 으로 접근
• DP에 저장할 값은 DP[i]번째 까지 왔을 때 점수의 최댓값이다. 계단의 점수가 stair 리스트에 저장되어 있다고 가정하고, 점화식을 만들어서 풀기

# 첫 번째 계단
DP[1] = stair[1]

# 두 번째 계단
DP[2] = stair[1] + stair[2] # 이경우 당연히 한번에 두 번째 칸에 가는것보다 첫번째를 밟고가야 큼

# 세 번째 계단, 이때 최댓값을 고른다.
DP[3] = stair[1] + stair[3] or stair[2] + stair[3] # 연속 세번은 안된다는 조건 때문에

# 네 번째 계산, 이때도 칸을 많이 밟는게 최댓값이므로 stair[2] + stair[4] 넘어간다.
DP[4] = stair[1] + stair[2] + stair[4] or stair[1] + stair[3] + stair[4] or stair[2] + stair[4]

먼저 작은 문제인 계단 한 칸, 두 칸 또는 세 칸을 오르는 경우에 대해 답을 구하고, 이를 활용하여 큰 문제인 n칸을 오르는 경우에 대해 답을 구하는 Bottom-up 방식으로 문제를 해결.

 

위 코드를 보면 네 번째는 첫 번째, 두 번째, 세 번째 와 겹치는 부분이 있다.  이 부분을 DP로 동일 계산에 대해 효율적으로 처리하게 해줄 수 있다.

DP[4] = DP[2] + stair[4] or DP[3] + stair[4]

이를 점화식으로 구현하면 다음과 같다!

DP[i] = max(DP[i-2] + stair[i], DP[i-3] + stair[i-1] + stair[i])

코드 구현

# 계단의 개수입력받기. 1 <= n <= 300
n = int(input())
# 계산의 숫자를 초기화, 1층은 1번째(not 0번째) 인덱스에 저장
stair = [0] * 301
for i in range(1, n+1):
	stair[i] = int(input())
# dp 테이블 초기화
dp = [0] * 301 # 첫 번째 계단부터 시작.
dp[1] = stair[1]
dp[2] = stair[1] + stair[2]
dp[3] = max(stair[1]+stair[3], stair[2]+stair[3])

# 점화식을 계산한다.
for i in range(4, n+1):
	dp[i] = max(dp[i-2]+stair[i], dp[i-3]+stair[i-1]+stair[i])
print(dp[n])

C++

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



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	
	int s[301] = { 0, }; // 계단 점수 저장 배열
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}

	// DP테이블 초기화
	int dp[301] = { 0, };
	dp[1] = s[1];
	dp[2] = s[1] + s[2];
	dp[3] = max(s[1] + s[3], s[2] + s[3]);

	for (int i = 4; i <= n; i++) {
		dp[i] = max(dp[i - 2] + s[i], dp[i - 3] + s[i - 1] + s[i]);
	}

	cout << dp[n];
	return 0;


}