백준 2096 - 내려가기(C++)

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다.

 

먼저 첫 줄에 적혀 있는 세 개의 숫자 중에서 하나를 골라 다음 줄로 차례대로 내려간다. 이때 다음의 조건이 있다.

 

파란 원은 갈 수 있는 공간이고 빨간 X는 갈 수 없는 공간이다.

 

이렇게 해서 최대 합과 최소 합을 구하는 문제이다.

 

입력

첫째 줄에 N이 입력된다. (1 <= N <= 100,000)

 

다음 N개의 줄에 숫자가 세 개씩 주어진다.

 

예제 입력

3
1 2 3
4 5 6
4 9 0

예제 출력

18 6

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 최대 합, 최소 합, 그리고 경로를 보아해서는 이 문제는 다이나믹 프로그래밍을 사용하는 것을 알 수 있다.

 

하지만 이 문제의 메모리 사용량 제한은 무려 4MB이다. 그리고 N개의 최대 범위는 100,000이다.

 

이 말은 함부로 캐시를 최대 범위 만큼 만들 수가 없다는 것이다.

 

그렇다면 한정된 메모리로 다이나믹 프로그래밍으로 문제를 풀어야 하는데, 이때 다음과 같은 아이디어가 떠올랐다.

 

아래로 차례대로 내려가면서 이전의 정보는 필요없지 않을까?

 

애초에 다이나믹 프로그래밍은 입력을 최소한 시켜야하고 다음의 값은 현재의 정보를 통해 정해지기 때문에 배열에 모든 입력값을 저장할 필요가 없다고 느껴졌다.

 

또한, 메모이제이션을 하고자 최대 범위 만큼의 캐쉬도 필요 없다고 느껴졌다.

 

그래서 고안한 방법이 다음과 같다.

첫 번째

우선 첫 번째 동작을 보면 첫 입력을 그대로 cost[]배열에 넣는다.

두 번째

 

그 다음 동작을 보면 두 번째 예제 입력을 기준으로 각 값이 더해질 수 있는 경우의 수 중 가장 큰 것을 선택해 다음 배열에 값을 갱신한다.

 

예를 들어, 위의 예제 입력 4라는 숫자는 1 혹은 2밖에 더해질 수 있다. 그렇기 때문에 1과 2중에 더 큰 2랑 더해져 2 + 4 = 6으로 다음 배열의 첫 번째 수가 갱신된 것이다.

 

이 방법을 방법하여 최종 값을 얻는다.

세 번째

마지막으로 위의 작업을 반복하여 최종 값이 담겨진 배열을 갇게 된다. 이때 가장 큰 숫자를 선택하여 정답을 구하면 된다.

 

최솟값은 이와 반대로 하면 된다.

 

코드

#include <iostream>

int dist1[3];
int dist2[3];

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N;
	std::cin >> N;
	int x, y, z;
	for (int i = 0; i < 3; i++)
	{
		int x;
		std::cin >> x;
		dist1[i] = x;
		dist2[i] = x;
	}
	int temp0 = 0, temp2 = 0;
	for (int i = 1; i < N; i++)
	{
		int x, y, z;
		std::cin >> x >> y >> z;
		temp0 = dist1[0];
		temp2 = dist1[2];
		dist1[0] = std::max(dist1[0], dist1[1]) + x;
		dist1[2] = std::max(dist1[1], dist1[2]) + z;
		dist1[1] = std::max(std::max(temp0, temp2), dist1[1]) + y;
		temp0 = dist2[0];
		temp2 = dist2[2];
		dist2[0] = std::min(dist2[0], dist2[1]) + x;
		dist2[2] = std::min(dist2[1], dist2[2]) + z;
		dist2[1] = std::min(std::min(temp0, temp2), dist2[1]) + y;
	}
	std::cout << std::max(std::max(dist1[0], dist1[1]), dist1[2]) << " " <<
		std::min(std::min(dist2[0], dist2[1]), dist2[2]) << std::endl;
	return 0;
}

문제 출처

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

2096번: 내려가기