C++ / 2579 / 계단 오르기 ( 다이나믹 프로그래밍 )

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

문제 요약

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임입니다.

그림과 깉이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 됩니다.

 

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

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

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

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

 

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

문제 풀이

1. 계단의 점수들을 입력받습니다.

2. dp 함수를 만드는데, 초깃값으로 

 

점수[1] = 계단[1]

점수[2] = 점수[1] + 계단[2]

점수[3] = 계단[2] + 계단[3] 과 계단[1] + 계단[3] 중에 더 큰값

주고, 4번째 경우부터 반복문을 돌립니다.

 

3. 반복문에서는

 

점수[현재 점수 -  2] + 계단[현재]

점수 [현재 점수 - 3] + 계단[현재] + 계단[현재 - 1]

중에 더 큰 값을 점수[현재 점수]에 넣어줍니다.

 

4. 출력으로 점수 배열의 원하는 인덱스를 출력합니다. 

주의할 점

dp 문제들은 점화식을 찾아 미리 경우의 수들을 저장해 두는 것이 관건인데, 점화식을 잘 못찾겠어서 다른 dp들을 풀어보고 다시 접근해보았던 문제였습니다.

계단 오르기의 점화식을 간략하게 보자면 3번째 칸 이후 부터는

3번 연속 밟으면 안된다는 규칙 때문에

전전칸 + 현재칸 ( 전칸을 건너뜀 ) 과 전전전칸 + 전칸 + 현재칸 ( 전전칸을 건너뜀 ) 중에 큰 값을 고르도록 프로그래밍 하였습니다. 

코드

#include<iostream>
#include<vector>

using namespace std;

vector<int> v;
int  p[304];

int n;

void dp()
{
	// 3번 칸 까지는 초기화
	p[0] = v[0];
	p[1] = v[1];
	p[2] = p[1] + v[2];
	p[3] = max(v[2] + v[3], v[1] + v[3]);

	for (int i = 4; i <= n; i++)
	{
		int a = p[i - 2] + v[i]; // 전칸을 안밟을경우
		int b = p[i - 3] + v[i] + v[i -1]; // 전전칸을 안밟을 경우
		p[i] = max(a, b); // 둘중 큰값 저장
	}
}
int main()
{
	cin >> n;

	v.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}
	dp();
	cout << p[n];
	return 0;
}

 

반응형

예제

6
10
20
15
25
10
20

결과