[백준 2096] 내려가기 - C언어(C++)

 

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

2096번: 내려가기

 문제 설명

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

 

 

---

해당 문제를 보니 큐를 사용하여 하나씩 내려오면 어떨까라는 생각이 가장 먼저 들었고 바로 구현에 들어갔다.

#include <iostream>
#include <queue>

using namespace std;

struct PosInfo {
	int y;
	int x;
	int score;
};

int n;
int map[100000][3];

void input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			cin >> map[i][j];
}

void sol() {
	int maxScore = -1;
	int minScore = 987654321;

	queue<PosInfo> q;
	q.push({ 0,0,map[0][0] });
	q.push({ 0,1,map[0][1] });
	q.push({ 0,2,map[0][2] });

	while (!q.empty()) {
		int y = q.front().y;
		int x = q.front().x;
		int score = q.front().score;
		q.pop();

		if (y == n - 1) {
			maxScore = maxScore > score ? maxScore : score;
			minScore = minScore < score ? minScore : score;
			continue;
		}
		
		switch (x) {
		case 0:
			q.push({ y + 1,0,score + map[y + 1][0] });
			q.push({ y + 1,1,score + map[y + 1][1] });
			break;
		case 1:
			q.push({ y + 1,0,score + map[y + 1][0] });
			q.push({ y + 1,1,score + map[y + 1][1] });
			q.push({ y + 1,2,score + map[y + 1][2] });
			break;
		case 2:
			q.push({ y + 1,1,score + map[y + 1][1] });
			q.push({ y + 1,2,score + map[y + 1][2] });
			break;
		}
	}

	cout << maxScore << ' ' << minScore;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	sol();
	return 0;
}

그러나, 결과는 메모리 초과

 

 map을 한 칸 내려간다고 했을 때, 내가 작성한 코드는 큐 안에 Idx=0인 곳에는 2개, Idx=1인 곳에는 3개, Idx=2인 곳에는 4개의 값이 들어가게 된다. 한 줄을 내려갈 때마다 9개의 요소가 들어가는 것이다.

그로 인해 메모리 초과가 나는 것 같았고 생각을 바꾸어 다이나믹 프로그래밍으로 구현하였다.

 

다이나믹 프로그래밍으로 구현할 때에는 크기가 3인 scores배열을 두었다. 한 줄을 내려갈 때마다 값이 들어올 수 있는 값들의 최댓값or최솟값을 넣으며, 계속해서 값을 갱신해주었다. 

 

 

<< 전체 코드 >>

#include <iostream>
#define MAX(a, b) ( (a)>(b)?(a):(b) )
#define MIN(a, b) ( (a)<(b)?(a):(b) )

using namespace std;

int n;
int map[100000][3];

void input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			cin >> map[i][j];
}

void sol() {
	// 최대 점수 구하기
	int scores[3] = { map[0][0], map[0][1], map[0][2] };

	int n0, n1, n2;
	for (int i = 1; i < n; i++) {
		n0 = map[i][0] +  MAX(scores[0], scores[1]);
		n1 = map[i][1] + MAX(MAX(scores[0], scores[1]), scores[2]);
		n2 = map[i][2] + MAX(scores[1], scores[2]);
		scores[0] = n0;
		scores[1] = n1;
		scores[2] = n2;
	}
	cout << MAX(MAX(scores[0], scores[1]), scores[2]) << ' ';

	// 최소 점수 구하기
	for (int i = 0; i < 3; i++)
		scores[i] = map[0][i];

	for (int i = 1; i < n; i++) {
		n0 = map[i][0] + MIN(scores[0], scores[1]);
		n1 = map[i][1] + MIN(MIN(scores[0], scores[1]), scores[2]);
		n2 = map[i][2] + MIN(scores[1], scores[2]);
		scores[0] = n0;
		scores[1] = n1;
		scores[2] = n2;
	}
	cout << MIN(MIN(scores[0], scores[1]), scores[2]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	sol();
	return 0;
}

이와 같이 제출하면 충분히 맞았습니다!! 를 볼 수 있다.