[백준] 2096번: 내려가기 (c++)

 

문제

---

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

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

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

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

2096번: 내려가기

 

문제조건

---

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

 

풀이

---

처음에는 무작정 모든 경우의 수를 다 구해보았다. n이 최대 100000이기 때문에 당연히 시간 초과가 난다. 어떤 값을 지나가는지가 중요하지 않고 규칙에 맞는 최대, 최소 값만을 구하면 된다. 따라서 한줄 한줄 읽어가며 그 값으로 나올 수 있는 최대, 최소 값을 업데이트 해주면 된다.

너무 어렵게 생각하지 말기...

 

코드

---

시간초과

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int num[100001][3];
int minValue = 1000000;
int maxValue = 0;


void downGame(int i, int cnt, int sum) {

	if (cnt == n) {
		if (sum > maxValue) maxValue = sum;
		if (sum < minValue) minValue = sum;
		return;
	}
	int il = i - 1;
	int ir = i + 1;
	if (il >= 0) {
		if (sum + num[cnt][il]) { downGame(il, cnt + 1, sum + num[cnt][il]); }
	}
	downGame(i, cnt + 1, sum + num[cnt][i]);
	if (ir < n) {
		downGame(ir, cnt + 1, sum + num[cnt][ir]);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> num[i][j];
		}
	}

	downGame(1, 0, 0);

	cout << maxValue << " " << minValue;
}

 

DP(정답)

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int num[100001][3];
int maxDp[3];
int minDp[3];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> num[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		maxDp[i] = num[0][i];
		minDp[i] = num[0][i];
	}

	for (int i = 1; i < n; i++) {
		int num0 = maxDp[0];
		int num2 = maxDp[2];
		maxDp[0] = max(maxDp[0], maxDp[1]) + num[i][0];
		maxDp[2] = max(maxDp[1], maxDp[2]) + num[i][2];
		maxDp[1] = max(max(num0, num2), maxDp[1]) + num[i][1];
	}

	for (int i = 1; i < n; i++) {
		int num0 = minDp[0];
		int num2 = minDp[2];
		minDp[0] = min(minDp[0], minDp[1]) + num[i][0];
		minDp[2] = min(minDp[1], minDp[2]) + num[i][2];
		minDp[1] = min(min(num0, num2), minDp[1]) + num[i][1];
	}
	cout << max(max(maxDp[0],maxDp[1]),maxDp[2]) << " " << min(min(minDp[0], minDp[1]), minDp[2]);
}