BOJ - 내려가기(C++)

문제 출처: https://www.acmicpc.net/problem/2096

문제 난이도

Gold 4(solved.ac 이용)

문제 접근법

처음엔 마지막 줄까지 가면 되는 거니깐 깊이 탐색을 사용했다.
시간초과가 나고 다른 사람 글을 참고하니 DP를 이용한다.

열은 3개로 정해져 있고 행만 변한다는 점에서 점화식을 세울 수 있다.
첫 번째 열, 바로 아래의 수와 그 옆만 체크 가능하다.
-> dp[i][0] = max(dp[i+1],[0] , dp[i+1],[1])
두 번째 열, 바로 아래의 수 3개 모두가 이동할 수 있다.
-> dp[i][0] = max(dp[i+1],[0], max(dp[i+1],[1] , dp[i+1],[2]))
세 번째 열, 바로 아래의 수와 그 옆.
-> dp[i][0] = max(dp[i+1][1], dp[i+1][2])

주의할 점!
메모리 제한이 4MB이기 때문에 dp 배열 값을 잘 생각해봐야한다.

전체 범위를 사용하지 않고 딱 두줄만 사용할 수 있다.
어차피 다음 줄로 넘어가면 그 이전의 이전의 줄은 사용하지 않기 때문이다.

통과 코드

#include <iostream>

using namespace std;

int arr[100001][3];
int mindp[2][3], maxdp[2][3];

int compareBigNum(int a, int b) {
	if (a < b) return b;
	else return a;
}
int compareSNum(int a, int b) {
	if (a > b) return b;
	else return a;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	mindp[0][0] = maxdp[0][0] = arr[0][0];
	mindp[0][1] = maxdp[0][1] = arr[0][1];
	mindp[0][2] = maxdp[0][2] = arr[0][2];

	for (int i = 1; i < N; i++) {
		maxdp[1][0] = arr[i][0] + compareBigNum(maxdp[0][0], maxdp[0][1]);
		maxdp[1][1] = arr[i][1] + compareBigNum(maxdp[0][2], compareBigNum(maxdp[0][0], maxdp[0][1]));
		maxdp[1][2] = arr[i][2] + compareBigNum(maxdp[0][1], maxdp[0][2]);
		
		maxdp[0][0] = maxdp[1][0];
		maxdp[0][1] = maxdp[1][1];
		maxdp[0][2] = maxdp[1][2];

		mindp[1][0] = arr[i][0] + compareSNum(mindp[0][0], mindp[0][1]);
		mindp[1][1] = arr[i][1] + compareSNum(mindp[0][2], compareSNum(mindp[0][0], mindp[0][1]));
		mindp[1][2] = arr[i][2] + compareSNum(mindp[0][1], mindp[0][2]);
		
		mindp[0][0] = mindp[1][0];
		mindp[0][1] = mindp[1][1];
		mindp[0][2] = mindp[1][2];
	}

	int maxVal = compareBigNum(maxdp[0][2], compareBigNum(maxdp[0][0], maxdp[0][1]));
	int minVal = compareSNum(mindp[0][2], compareSNum(mindp[0][0], mindp[0][1]));

	cout << maxVal << ' ' << minVal << "\n";
	
	return 0;
}

피드백

시간초과

첫 줄에서 마지막 줄에서 끝나니깐 dfs를 생각했다.
바로 아래의 수와 접점이니깐 y의 -1,+1만 줘서 0~2 범위를 넘어가면 무시하는 식으로 짰다.
시간 제한이 1초지만 범위가 십만이라 괜찮을 줄 알았는데 시간초과 났다.

int arr[100001][3];
int dy[3] = { 0, -1, 1 };
int N;
int maxV = -1, minV = 987654321;

void dfs(int x, int y, int sum) {
	if (x == N - 1) {
		if (sum > maxV) maxV = sum;
		if (sum < minV) minV = sum;
		return;
	}
	for (int i = 0; i < 3; i++) {
		int nx = x + 1;
		int ny = y + dy[i];
		if (ny < 0 || ny >= 3) continue;
		dfs(nx, ny, sum + arr[nx][ny]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 3; i++) {
		dfs(0, i, arr[0][i]);
	}
	cout << maxV << " " << minV << "\n";
	
	return 0;
}

메모리 초과

int arr[100001][3];
int mindp[100001][3], maxdp[100001][3];

int compareBigNum(int a, int b) {
	if (a < b) return b;
	return a;
}
int compareSNum(int a, int b) {
	if (a > b) return b;
	return a;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	mindp[0][0] = maxdp[0][0] = arr[0][0];
	mindp[0][1] = maxdp[0][1] = arr[0][1];
	mindp[0][2] = maxdp[0][2] = arr[0][2];

	for (int i = 1; i < N; i++) {
		maxdp[i][0] = arr[i][0] + compareBigNum(maxdp[i-1][0], maxdp[i - 1][1]);
		maxdp[i][1] = arr[i][1] + compareBigNum(maxdp[i - 1][2], compareBigNum(maxdp[i - 1][0], maxdp[i - 1][1]));
		maxdp[i][2] = arr[i][2] + compareBigNum(maxdp[i - 1][1], maxdp[i - 1][2]);

		mindp[i][0] = arr[i][0] + compareSNum(mindp[i - 1][0], mindp[i - 1][1]);
		mindp[i][1] = arr[i][1] + compareSNum(mindp[i - 1][2], compareSNum(mindp[i - 1][0], mindp[i - 1][1]));
		mindp[i][2] = arr[i][2] + compareSNum(mindp[i - 1][1], mindp[i - 1][2]);
	}

	int maxVal = compareBigNum(maxdp[N- 1][2], compareBigNum(maxdp[N - 1][0], maxdp[N - 1][1]));
	int minVal = compareSNum(mindp[N - 1][2], compareSNum(mindp[N - 1][0], mindp[N - 1][1]));

	cout << maxVal << ' ' << minVal << "\n";
	
	return 0;
}