https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
문제 해결 과정
착안
정해진 규칙에 따라 계단을 오를 때 점수를 누적하므로 동적계획법(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;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 1181번: 단어 정렬 (0) | 2023.06.11 |
---|---|
[Baekjoon] 11650번: 좌표 정렬하기 (0) | 2023.06.11 |
[Baekjoon] 1920번: 수 찾기 (0) | 2023.06.09 |
[Baekjoon] 7785번: 회사에 있는 사람 (0) | 2023.06.07 |
[Baekjoon] 1932번: 정수 삼각형 (0) | 2023.06.05 |
댓글