BOJ (C/C++) 2096번: 내려가기

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

2096번: 내려가기

---

풀이

총 30만 칸에 최소, 최대값을 포함한 DP 배열을 만들어 i 번째 칸에 도착했을 때의 최소, 최대값을 저장했다.

 

처음엔 DP 배열과 값을 받는 배열 2개를 생성했으나 이렇게 할 경우 메모리가 초과되어 초기값을 DP 배열에 저장하고, 값을 더해가는 방식을 사용했다.

---

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int DP[100000][3][2];

int Get(int a, int b, int c, bool min) {
	int m, M;
	if (a > b) {
		if (b > c) m = c, M = a; // a>b>c

		else { // c>=b
			if (c > a) m = b, M = c; // c>a>=b
			else m = b, M = a; // a>=c>=b
		}
	}
	else { // b>=a
		if (a > c) m = c, M = b; // b>=a>c

		else { //c>=a
			if (c > b) m = a, M = c; // c>b>=a
			else m = a, M = b; // b>=c>=a
		}
	}
	if (min) return m;
	else return M;
}

int main() {
	int N, min, Max;
	int a, b, c;

	// input
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d", &a, &b, &c);
		DP[i][0][0] = DP[i][0][1] = a;
		DP[i][1][0] = DP[i][1][1] = b;
		DP[i][2][0] = DP[i][2][1] = c;
	}

	for (int i = 1; i < N; i++) {
		int m1 = DP[i - 1][0][0], m2 = DP[i - 1][1][0], m3 = DP[i - 1][2][0],
			M1 = DP[i - 1][0][1], M2 = DP[i - 1][1][1], M3 = DP[i - 1][2][1];

		// 1, 3번째 칸 최소, 최대 값 구하기
		DP[i][0][0] += m1 < m2 ? m1 : m2, DP[i][2][0] += m2 < m3 ? m2 : m3;
		DP[i][0][1] += M1 > M2 ? M1 : M2, DP[i][2][1] += M2 > M3 ? M2 : M3;

		// 가운데 칸의 최소, 최대 값 구하기
		min = Get(m1, m2, m3, true), Max = Get(M1, M2, M3, false);
		DP[i][1][0] += min;
		DP[i][1][1] += Max;
	}

	// print
	printf("%d ", Get(DP[N - 1][0][1], DP[N - 1][1][1], DP[N - 1][2][1], false)); // max
	printf("%d", Get(DP[N - 1][0][0], DP[N - 1][1][0], DP[N - 1][2][0], true)); // min
	return 0;
}