< 백준 BaekJoon : 2579번 계단 오르기 > C++

<< 문제 >>

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

2579번: 계단 오르기

 

 

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

이 세가지 규칙을 만족시키기 위해서는 이어진 3개의 계단 중 2개를 택해야 한다. 

그보다 적게 선택할 수도 있지만, 굳이 최대값을 구함에 있어서 적게 선택할 필요가 없다.

 

각 계단마다 2개의 공간을 가지는 배열을 할당했다. 

arr[i] = [ i-1번째를 선택했을 때 최대값, i-2번째를 선택했을 때의 최대값 ]

 

이때, 3개 연속은 선택할 수 없으므로 i -1번째는 [0]과 [1] 중 1에서만 선택이 가능하다. 

 

결국 

 

arr[i][0] += arr[i - 1][1];
arr[i][1] += max(arr[i - 2][0], arr[i - 2][1]);

 

로 점화식이 만들어진다. 

 

이를 바탕으로 진행하면 마지막 arr[num-1]의 0과 1에 값이 만들어지고, 둘 중 최대값을 출력하면 된다.

 

<< 코드 >>

 

#include <iostream>
using namespace std;


int arr[300][2];

int main() {

	int num;
	cin >> num;

	for (int i = 0; i < num; i++) {

		int temp;
		cin >> temp;
		arr[i][0] = temp;
		arr[i][1] = temp;

	}

	arr[1][0] += arr[0][0];

	for (int i = 2; i < num; i++) {
		arr[i][0] += arr[i - 1][1];
		arr[i][1] += max(arr[i - 2][0], arr[i - 2][1]);
	}
	cout << max(arr[num-1][0],arr[num-1][1]) << endl;
}

 

<< 깃헙 >>

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/2579.%E2%80%85%EA%B3%84%EB%8B%A8%E2%80%85%EC%98%A4%EB%A5%B4%EA%B8%B0