TIL baekjoon

[baekjoon/c++] 계단 오르기 - 2579 : 메모이제이션

[Silver III] 계단 오르기 - 2579

문제 링크

성능 요약

메모리: 2156 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 2일 17:38:42

문제 설명

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

<그림 1>

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

<그림 2>

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

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

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

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

입력

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

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

출력

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

제출코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
using namespace std;
int N;
int stair[300];
map<pair<int, bool>, int> memo;

int fullSearch(int n, bool flag) {
	auto key = make_pair(n, flag);
	if (memo.find(key) != memo.end()) {
		return memo[key];
	}
	if (n >= N) {
		return 0;
	}
	if  (flag) {
		memo[key] = (stair[n] + fullSearch(n + 2, false));
		return memo[key];
	}
	else {
		memo[key] = (stair[n] + max(fullSearch(n + 1, true), fullSearch(n + 2, false)));
		return memo[key];
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	for (int i = N-1; i >= 0; i--)
	{
		int n;
		cin >> n;
		stair[i] = n;
	}

	cout << fullSearch(0,0);

	return 0;
}

과정

일단은 그림부터 골치가 아팠는데, 특히 조건 2. 연속된 세개의 계단을 밟으면 안된다는 전제가 풀이 방법을 떠올리는데 시간이 조금 걸렸다.

조건 3. 마지막 도착계단을 반드시 밟아야 하기에 시작지점을 뒤에서부터 놓는 식으로 구현하였다.

재귀함수로 해결하고자 하였고, 처음에는 메모리제이션을 사용하지 않고 피보나치 수열의 재귀함수 모양처럼 계속해서 뻗어나가는 식으로 탐색을 진행하였다.

그러면서 flag를 사용해 연달아 n+1로 진행한 함수건에 대하여 다음 재귀 호출시 n+2로 강제하여 진행하였다.

다만 나무가지처럼 계속해서 뻗어 나가는 형태이기에 깊이도 n, 각각 f(n) 에 대해 f(n+1) f(n+2)가 호출되니 계속 두배씩 늘어난다.. 즉,

복잡도는 O(n^2) 이기에 시간초과로 해결할 수 없었고, 메모리제이션을 활용해 해결하였다.

pair와 map

달랐던 점은 map의 키값으로 pair쌍이 들어간다는 것이였다!

"왜냐면 n, flag에 따라 값을 따로 저장해야하니깐 말이다"

그래서 pair<n,flag> 로 묶어 키값을 구성하여 진행하였다.

*unordered_map은 커스텀 해쉬 함수를 추가로 구현해주어야하기 때문에 map으로 진행하였다.