[Baekjoon] 2579번: 계단 오르기

 

 

 

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

2579번: 계단 오르기

 

---

 

문제 해결 과정

착안

정해진 규칙에 따라 계단을 오를 때 점수를 누적하므로 동적계획법(dynamic programming)을 이용하며, 규칙에 따라 식을 세우는 것에 의하여 문제를 해결하고자 하였다.

 

구현

문제에서 주어지는 규칙 중에서 연달아 3 개의 계단을 오를 수 없다는 규칙에 의해, $i$ 번째 계단($i \geq 3$)에 도착했을 때 누적 점수의 최댓값을 아래와 같이 구해야 한다(편의상 $i = 0$ 인 경우는 점수가 0인 상태인 시작점을 의미).

 

• $(i-3)$ 번째 계단에서 $(i-1)$ 번째 계단을 거쳐 $i$ 번째 계단에 도달하는 경우
• $(i-2)$ 번째 계단에서 $i$ 번째 계단에 바로 도달하는 경우

 

따라서, $i$ 번째 계단의 점수를 $s_i$ 라고 하고, $i$ 번째 계단에 도착했을 때 누적 점수의 최댓값을 $S_i$ 라고 하면 다음과 같이 누적 점수의 최댓값에 대한 점화식을 구할 수 있다(위에서와 같이 $i = 0$ 인 경우는 시작점을 의미).

$$S_i = s_i + \max (S_{i-2}, \space S_{i-3} + s_{i-1}) \quad (i \geq 3)$$

$$S_0 = s_0 = 0$$

$$S_1 = s_1$$

$$S_2 = s_1 + s_2$$

 

위의 식에서 $s_i$ 의 값과 $S_i$ 의 값을 모두 가지고 있어야지만 다음 번째 누적 점수의 최댓값을 구할 수 있으므로, 계단 자체의 점수 $s_i$ 와 누적 점수 $S_i$ 를 저장할 배열을 별도로 선언하여 사용해야하는 점을 고려하여 프로그래밍하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Stairs[301];
int Scores[301];

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

	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> Stairs[i];

		if (i > 2)
		{
			int score = Stairs[i - 1] + Scores[i - 3];
			Scores[i] = Stairs[i] + (Scores[i - 2] > score ? Scores[i - 2] : score);
		}
		else if (i == 1)
			Scores[i] = Stairs[i];
		else if (i == 2)
			Scores[i] = Stairs[i] + Stairs[i - 1];
	}

	cout << Scores[N] << "\n";
	return 0;
}

 

 

[스포 주의] (번외: 메모리 최적화) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Stairs[301];

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

	int N;
	cin >> N;

	int dp[4] = { 0, };
	for (int i = 1; i <= N; i++)
	{
		cin >> Stairs[i];

		if (i > 2)
		{
			int score = Stairs[i - 1] + dp[0];
			dp[3] = Stairs[i] + (dp[1] > score ? dp[1] : score);

			dp[0] = dp[1];
			dp[1] = dp[2];
			dp[2] = dp[3];
		}
		else if (i == 1)
			dp[1] = Stairs[1];
		else if (i == 2)
			dp[2] = Stairs[1] + Stairs[2];
	}

	cout << (N > 2 ? dp[3] : dp[N]) << "\n";
	return 0;
}

 

실행 결과