2579 계단 오르기

계단오르기 (2579)

 

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

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

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

---

 

풀이코드 ( 재귀 활용한 메모이제이션 )

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
// 2579 계단 오르기 완전 탐색

const int MAX = 300;
int n;
// cache[i][j] 는 최댓값을 저장함과 동시에 연속성을 판별한다.
int seq[MAX], cache[MAX][2];
int max(int a, int b) {return a < b ? b : a;}

// 해당 인덱스에서의 최대 값을 반환한다.
int stair(int end, int flag){
	// 기저사례 : 범위 밖이면 0
	if(end < 0) return 0;
	// 기저사례 : 도착하면 끝
	if(end == 0) return seq[0];

	int& ret = cache[end][flag];
	// 구했으면 바로 리턴
	if(ret != -1) return ret;

	if(flag == 1) // 연속이라면
		return ret = stair(end - 2, 0) + seq[end];
	if(flag == 0) // 비연속이라면
		return ret = max(stair(end - 1, 1) + seq[end], stair(end - 2, 0) + seq[end]);
}

int main(){

	cin >> n;
	cin.ignore();

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

	 memset(cache, -1, sizeof(cache));
	cout << stair(n - 1, 0) << endl;
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

최적화 문제 동적 계획법 레시피

1. 모든 답을 만들어보고 최적해를 반환하는 완전 탐색 알고리즘을 설계
2. 전체 답의 점수를 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꿈.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보는 꼭 필요한 것만 남기고 줄인다.
4. 입력이 배열이거나 문자열이라면 적절한 변환을 통해 메모이제이션 하도록 한다.
5. 메모이제이션 적용 

메모이제이션 구현 패턴

굉장히 자주 접하게 될 메모이제이션은 한 가지 패턴을 정해두고 항상 같은 형태로 구현 하면 버그를 찾기도, 작성하기 도 쉬워집니다.

1. 항상 기저 사례를 먼저 처리합니다. 입력이 범위를 벗어난 경우 등.

2. cache 를 초기화합니다. -1로 할지 numeric_limits 로 할지 등은 문제에 따라 정합니다.

3. ret 가 cache 의 참조형으로 사용된다. 고차원 배열에서의 인덱스 실수를 없애준다.

4. 메모이제이션용 배열을 초기화하는 방법을 알아두자. 정수형일 경우 memset 이 도움된다.

메모이제이션 시간 복잡도 분석

주먹구구식으로 이를 짐작해봅시다.

(존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

이러한 방식으로 수행 시간의 상한 을 짐작해 볼 수 있다.

 

풀이

지난번에 풀었던 와인 마시기 문제와 동일했다. 와인잔 문제 마시기와 점화식까지 동일하다고 볼 수 있었다. 하지만, 이번 경우에는 종만북의 메모이제이션 레시피에 따라서 풀어보았다. 만약 이러한 문제를 마주했을 때, 점화식을 찾아내지 못한다면 이러한 방법이 매우 도움이 될 듯 하다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 재귀를 return 할 때 어떻게 무엇을 return 할지를 잘 생각해봤어야 했다. return 값을 착오하여 많은 시간을 허비했다.

- n - 1 번째 idx 에서 시작하여 0번째 idx 를 향해 내려가는데 만약, 1번째 계단에서 2칸 내려갔다면 그냥 그 칸은 없는 것으로 0을 리턴하면 됐었다. 왜냐하면 그렇게 내려가는 방법 또한 규칙에 어긋나지 않기 때문이다. 하지만, 그것이 규칙에 어긋난다고 생각했었어서 범위 밖일 때, min 값을 반환하도록 했었는데 이것이 오답의 원인이 되었었다.

- 완전 탐색 구현 - 남은 선택들에 대한 값 반환하도록 부분 문제 수정 - 3연속 안된다는 조건을 고려하여 cache 배열을 2차원으로 적절히 변형하여 메모이제이션 가능케함 - 메모이제이션

위와 같은 방식으로 문제를 풀어나갔는데 상당히 논리적이었다고 생각한다. 물론 점화식을 찾아내어 프로그래밍 하는 것이 속도 면에서 월등하겠다.

점화식은 아래를 참고하자.

2579번 계단 오르기 문제 풀이