💻코딩테스트/백준

[백준/C++] 2579번 : 계단 오르기 - DP/점화식 연습

공대 컴린이 2023. 6. 12. 18:16
728x90

계단 오르기

 

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1 

6
10
20
15
25
10
20

예제 출력 1 

75

동적 계획법을 이용한 코딩테스트 문제를 연습하면서 DP 대표 유형 중 하나인 계단 오르기 문제를 풀어보았다.

계단 오르기 문제는 이전에 유튜브에서 풀이 방법을 봤는데도 직접 풀려니까 안풀려서 너무 어려웠다..

 

DP 문제의 핵심은 언제나 '점화식'을 세우는 것이다.

계단 오르기의 점화식을 세우기 위해 N번째 계단을 오르는 경우에 나타날 수 있는 경우의 수를 전부 따져봐야 한다.

 

N 번째 계단에 오르는 경우의 수는

n-1 칸에서 1칸 오르고 이전에 연속으로 계단을 오르지 않은 경우와,

n-2 칸에서 2칸 오르고 이전에는 한칸/두칸 상관없이 계단을 오를 수 있는 경우가 있다.

 

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

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

	// [n][m] : n 몇번째 계단, m 몇번 연속 (3번 연속은 안되므로 2까지 선언)
	// m = 0 : 1번 연속, m = 1 : 2번 연속
	int dp[301][2];
	int stair[301];

	int stairCnt;
	cin >> stairCnt;

	for (int i = 1; i <= stairCnt; i++)
		cin >> stair[i];

	dp[1][0] = stair[1]; // 첫번째 계단 초기화

	for(int i = 2; i <= stairCnt; i++)
	{
		dp[i][1] = dp[i - 1][0] + stair[i];
		dp[i][0] = max(dp[i - 2][1], dp[i - 2][0]) + stair[i];
	}

	cout << max(dp[stairCnt][0], dp[stairCnt][1]);

	return 0;
}

 

풀이 코드를 보면 dp 배열이 2차원 배열 [n][m]으로 이루어져 있다.

n은 몇번째 계단을 오른 것인지를 저장하고, m은 몇번 연속으로 계단을 올랐는지를 저장한다.

 

문제에서는 3번 연속으로 계단을 연속하여 오를 수 없다고 제한했기 때문에 [m]은 [2]까지만 선언하였다.

따라서 m 이 [0] 값이면 1번 연속으로 계단을 오른 것, [1] 값이면 2번 연속으로 계단을 오른 것으로 판별하였다.

 

계단의 각 점수를 입력받아서 stair 변수에 초기화 한 뒤, 점화식을 세워 2부터 계단 개수만큼의 for문을 수행해주었다.

 

이후 위에서 찾았던 계단을 오르는 두 가지 경우에 대한 점화식을 각각 세워보았다.

 

1️⃣ n-1 칸에서 1칸 오르고 이전에 연속으로 계단을 오르지 않은 경우

 

dp[n][1] = dp[n - 1][0] + stair[n];

 

한 칸의 계단을 연속으로 오르기 때문에 dp[n]의 두번째 원소가 [0]이 아니라 [1]이 된다.

또한 n-1 칸에서 계단을 오를때에는 이전 계단(n-1)이 절대 2번 연속으로 오르지 않은 경우여야만 한다. 2번 연속 오른 경우에 n번째 계단을 오르면 3번 연속으로 문제 규칙에 위배되기 때문이다.

따라서 dp[n - 1][0]인 경우와 n번째 계단의 값(stair[n])을 더한다.

 

2️⃣ n-2 칸에서 2칸 오르고 이전에는 한칸/두칸 상관없이 계단을 오를 수 있는 경우

 

dp[n][0] = (dp[n - 2][0] or dp[n - 2][1]) + stair[n];

 

n-2칸에서 2칸을 오를 때에는 1번 연속이 되므로 dp[n]의 [0] 이 된다.

또한 마지막 계단을 2칸 올랐을 때에는 n-2 칸에 도달할때 한 칸을 올라가든, 두 칸을 올라가든 상관 없기 때문에 두 가지 경우의 dp 값 중 더 큰 최댓값을 선택하여 더해주었다.

따라서 dp[n -2][0] 과 dp[n - 2][1] 중에 최댓값을 뽑고 거기에 n번째 계단의 점수를 더한다.

 

이렇게 구해진 dp 값에서 두 경우 중 더 값이 큰 경우를 max 함수로 비교하여 최종 출력하면 문제가 해결 된다.

728x90