[백준 2579번 C++] 계단 오르기

1. 문제 링크

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

2. 문제 설명

계단의 개수와 각 계단의 점수를 입력받아, 계단 오르기 게임에서 얻을 수 있는 총점수의 최댓값을 출력하는 문제입니다.

계단 오르기 게임의 규칙은 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

 

 

3. 소스코드

BOJ 2579번 계단 오르기 C++ 풀이입니다.

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

int d[300][2];
int step[300];

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> step[i];

	d[0][0] = step[0];
	d[1][0] = step[1];
	d[1][1] = step[0] + step[1];
	for (int i = 2; i < n; i++) {
		d[i][0] = max(d[i - 2][0], d[i - 2][1]) + step[i];
		d[i][1] = d[i - 1][0] + step[i];
	}
	cout << max(d[n - 1][0], d[n - 1][1]);

	return 0;
}

5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 계단의 개수의 최댓값인 300크기의 int형 배열을 선언합니다. 계단 오르기 게임의 규칙이 한 번에 한 계단씩 또는 두 계단씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟아서는 안 되므로, 이 조건을 검사하기 위해 d[i][0]에는 계단을 연속해서 밟지 않는 경우(즉, i -2번째 계단을 밟은 후 i번째 계단을 밟는 경우)의 최대 점수값을 저장하고, d[i][1]에는 계단을 연속해서 밟는 경우(즉, i - 1번째 계단을 밟은 후, i번째 계단을 밟는 경우)의 최대 점수 값을 저장합니다.

6번 라인 : 각 계단의 점수를 저장할 step 배열을 선언합니다. 역시 계단의 개수의 최댓값이 300이므로 크기는 300으로 선언했습니다. d배열과 step배열 모두 0으로 초기화하기 위해 전역변수로 선언했습니다.

16번 라인 : 각 계단의 점수를 입력받아 step배열에 저장합니다. 문제에서는 1번째부터 시작하지만 편의를 위해 0번째부터 저장했습니다.

18번 라인 : 0번째 계단은 연속해서 밟을 수 없으므로 d[0][0]만 가능하므로 d[0][0]에 0번째 계단의 점수를 저장합니다.

19번 라인 : 1번째 계단은 연속해서 밟지 않는 경우 바로 1번째 계단을 밟는 것이기 때문에 d[1][0]에 1번째 계단의 점수를 저장합니다.

20번 라인 : 1번째 계단은 연속해서 밟는 경우, 0번째 계단, 1번째 계단을 밟는 것이기 때문에 d[1][1]에 0번째 계단의 점수와 1번째 계단의 점수의 합을 저장합니다.

21번 라인 : 2번째 계단부터 n - 1번째 계단까지 for문을 돌면서

22번 라인 : d[i][0]번째 계단에는 계단을 연속해서 밟지 않는 경우를 저장하기 때문에, i-2번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 따라서 i-2번째 계단을 밟을 때 얻을 수 있는 점수인 d[i - 2][0]과 d[i - 2][1] 중에서 큰 값과 i번째 계단의 값을 더해서 저장합니다.

23번 라인 : d[i][1]번째 계단에는 계단을 연속해서 밟는 경우를 저장하기 때문에 i-1번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 연속된 세 개의 계단을 밟을 수 없으므로 d[i - 1][1]을 선택할 수 없습니다. 따라서 d[i - 1][0]에 저장된 점수에 i번째 계단의 값을 더해서 저장합니다.

25번 라인 : 계단의 점수를 입력받을 때 0번째 부터 입력받았으므로, 최종적으로 n - 1번째 계단을 밟았을 때의 점수 중에서 큰 값을 출력합니다.