BOJ 2096 : 내려가기

알고리즘 문제 전체 링크

 

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

 

 

메모리가 4MB로 매우 작은 상태에서 다이나믹 프로그래밍으로 문제를 풀어야 한다.

아래의 4개의 배열로 문제를 풀 수 있다.

int A[4]; /* 작은 값 저장 */
int B[4]; /* 큰 값 저장 */
int C[4]; /* 입력 값 */
int D[4]; /* temp 값 */

 

N번째 내려가기를 했을 때 얻을 수 있는 최소값은 3가지 경우로 나뉜다.

 

세 개의 수 중 

첫 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수를 선택한 경우.

두 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수/세 번째 수를 선택한 경우.

세 번째 수를 선택한 경우 - 이전 값에서 두 번째 수/세 번째 수를 선택한 경우.

 

따라서 아래와 같은 공식이 만들어진다.

scanf("%d %d %d", &C[1], &C[2], &C[3]);

D[1] = minValue(A[1] + C[1], A[2] + C[1]);
D[2] = minValue(A[1] + C[2], minValue(A[2] + C[2], A[3] + C[2]));
D[3] = minValue(A[3] + C[3], A[2] + C[3]);

 

scanf로 N번째 입력값을 C[1,2,3]로 받았을 때,

C[1]을 선택하였다면, 그 동안 누적된 점수 A[1] 또는 A[2]에서 내려온 경우이다.

따라서 둘 중 작은 값을 D[1]에 저장한다.

 

C[2]의 경우는 A[1,2,3]에서 모두 내려올 수 있기 때문에 D[2]의 공식이 조금 더 길어진다.

만들어진 D는 다시 누적값인 A로 옮겨주면 된다.

 

큰 값에 대한 것은 B에 누적하면 된다.

D[1] = maxValue(B[1] + C[1], B[2] + C[1]);
D[2] = maxValue(B[1] + C[2], maxValue(B[2] + C[2], B[3] + C[2]));
D[3] = maxValue(B[3] + C[3], B[2] + C[3]);

B[1] = D[1];
B[2] = D[2];
B[3] = D[3];

이 과정에서 이전 누적값만 필요하기 때문에 적은 메모리로 다이나믹 프로그래밍을 할 수 있다.

 

초기값에 대해 예외처리를 해주면 코드가 완성된다.

#include <stdio.h>

int N, M, K;
int A[4]; /* 누적된 작은 값 저장 */
int B[4]; /* 누적된 큰 값 저장 */
int C[4]; /* 입력 값 */
int D[4]; /* temp 값 */

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

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

int main()
{
	scanf("%d", &N);

	scanf("%d %d %d", &A[1], &A[2], &A[3]);

	B[1] = A[1];
	B[2] = A[2];
	B[3] = A[3];

	for (int i = 2; i <= N; i++)
	{
		scanf("%d %d %d", &C[1], &C[2], &C[3]);

		D[1] = minValue(A[1] + C[1], A[2] + C[1]);
		D[2] = minValue(A[1] + C[2], minValue(A[2] + C[2], A[3] + C[2]));
		D[3] = minValue(A[3] + C[3], A[2] + C[3]);

		A[1] = D[1];
		A[2] = D[2];
		A[3] = D[3];

		D[1] = maxValue(B[1] + C[1], B[2] + C[1]);
		D[2] = maxValue(B[1] + C[2], maxValue(B[2] + C[2], B[3] + C[2]));
		D[3] = maxValue(B[3] + C[3], B[2] + C[3]);

		B[1] = D[1];
		B[2] = D[2];
		B[3] = D[3];
	}

	printf("%d %d\n", maxValue(B[1], maxValue(B[2], B[3])), minValue(A[1], minValue(A[2], A[3])));

	return 0;
}