[백준][C] 2096번 내려가기

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

 

밑으로 쭉쭉 내려가면서 어떻게 더해야 최대인지 최소인지 구하는 문제이다.

 

예제 1을 보면서 생각을 해보자

 

 

여기서의 최대값은 18로 3 + 6 + 9 의 경로로 완성된다. 최소값은 6으로 1 + 5 + 0 의 경로로 완성된다.

 

만약 최소값을 구할 때 1 -> 4 루트로 갔다면 4와 9밖에 가지 못하니 최소값을 구하지 못하게 된다.

 

이렇듯 가장 최소만 고르면 답을 찾지 못하게 되므로 많은 경우의 수를 고려해봐야한다.

 

하지만 이렇게 생각해보자.

지금까지 내려왔을 때 이게 가장 최소값임을 확인할 수 있으면 그 값에 가장 작은 값을 더해주면 최소값을 구할 수 있을 것이다.

 

예를 들어 0의 기준에서 살펴보자

0으로 이동할 수 있는 칸은 5와 6이다.

0의 입장에서 5가 6보다 작으니 최소값을 구하기 위해선 5를 더해야한다.

 

이 경우엔 정답이지만 함정에 빠질 수 있으니 올라가본다.

5에 갈 수 있는 것은 1, 2, 3이다.

그렇다면 1 -> 5 를 거쳐온 값이 가장 작게된다. (6의 경우 2, 3이 가능하니)

 

즉 칸을 한칸 씩 내려갈 때 밑의 칸은 위의 같에서 접근 가능한 칸 중 가장 작은 칸을 더해준다.

이렇게 누적합을 쌓아가면서 내려가다보면 해당 칸은 그 칸에 가능한 경로중 가장 작은 값이 된다. (시작점부터 쌓아왔다면)

 

즉, 각 칸이 그 칸에서 가능한 가장 작은 값이 된다.

 

N개의 줄이 있을 때 1부터 시작해서 정답을 쌓아가면서 재활용하는 이러한 방법을 Dynamic Programming 이라고 한다.

(동적 계획법이라고 하는데 오히려 기억하며 풀기가 더 맞는 표현이라고 한다.)

 

어떤 거대한 문제가 작은 문제의 중복으로 구성되었다면  (위의 표처럼 과정을 똑같은데 길이만 길어지는)

작은 문제를 해결하고 이 결과값을 가지고 문제를 점점 키워가면서 해결하는 것이다.

 

대표적으로 피보나치 수열이 있는데 F(n) = F(n-1) + F(n-2) 을 구할 때 F(n-1)과 F(n-2)를 각각 처음부터 구하는 것이 아닌 F(0) + F(1) 부터 시작해서 F (n-1)과 F(n-2)를 둘 다 구한 뒤 그 값으로 F(n)을 구하는 것이다.

 

이 경우 한번의 연산으로 F(n-1)과 F(n-2)를 둘다 구하기 때문에 속도가 빠르게 된다.

 

 

이제 다시 본 문제로 돌아가서

 

위에서 말한대로 누적값을 구하기 위해 N의 최대값만큼 배열을 구성해 값을 입력받고 내려가면서 누적값을 구하면 좋겠지만

 

아쉽게도 메모리가 4 MB로 크게 제한적이다. (이전 문제인 분수 합에서 메모리가 128 MB 였다.)

그래도 혹시 몰라서 구현해봤는데 바로 메모리 초과가 발생했다.

 

이 방법은 간단하게 해결했다.

문제에서 원하는 답은 가장 마지막까지 계산한 결과값으로 중간값은 필요가 없다.

그렇다면 누적합을 구하고 이전 값들은 버리면 된다.

 

그래서 배열을 3개 3개로 총 6개만 만들어서 이전, 현재만 남기고 나머지 값은 버리도록 했다.

최소값도 같은 방식으로 구현하면 된다.

 

밑은 C로 구현한 코드이다.

 

 

#include <stdio.h> 
#pragma warning(disable:4996)

int max(int a, int b)
{
	return a > b ? a : b;
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int main()
{
	int map[3];
	int maxArr[2][3] = { 0 };
	int minArr[2][3] = { 0 };
	int N, maxV;

	scanf("%d", &N);

	scanf("%d %d %d", &map[0], &map[1], &map[2]);
	maxArr[1][0] = map[0];
	maxArr[1][1] = map[1];
	maxArr[1][2] = map[2];

	minArr[1][0] = map[0];
	minArr[1][1] = map[1];
	minArr[1][2] = map[2];

	for (int i = 1; i < N; i++)
	{

		for (int j = 0; j < 3; j++)
		{
			maxArr[0][j] = maxArr[1][j];
			minArr[0][j] = minArr[1][j];
		}

		scanf("%d %d %d", &map[0], &map[1], &map[2]);

		maxArr[1][0] = max(maxArr[0][0], maxArr[0][1]) + map[0];
		maxArr[1][1] = max(maxArr[0][0], max(maxArr[0][1], maxArr[0][2])) + map[1];
		maxArr[1][2] = max(maxArr[0][1], maxArr[0][2]) + map[2];

		minArr[1][0] = min(minArr[0][0], minArr[0][1]) + map[0];
		minArr[1][1] = min(minArr[0][0], min(minArr[0][1], minArr[0][2])) + map[1];
		minArr[1][2] = min(minArr[0][1], minArr[0][2]) + map[2];
	}

	printf("%d %d\n", max(maxArr[1][0], max(maxArr[1][1], maxArr[1][2])), min(minArr[1][0], min(minArr[1][1], minArr[1][2])));

	return 0;
}

 

글솜씨가 좋지 않아 이 글은 내가 다시 읽어봐도 이해가 잘 안될 것 같다.

좀 더 공부를 하면서 설명을 잘하게 되면 이 글을 다시 쓰고 싶다.