<백준 알고리즘> 2096번: 내려가기

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

예제 입력 1

3 1 2 3 4 5 6 4 9 0

예제 출력 1

18 6

예제 입력 2

3 0 0 0 0 0 0 0 0 0

예제 출력 2

0 0

---

Solution

#include<stdio.h>
#include<stdlib.h>

int max3(int x,int y,int z)
{
	if(x>=y&&x>=z)
		return x;
	else if(y>=x&&y>=z)
		return y;
	else
		return z;
}

int min3(int x,int y,int z)
{
	if(x<=y&&x<=z)
		return x;
	else if(y<=x&&y<=z)
		return y;
	else
		return z;
}

int main(void)
{
	int N, score[2][3], max[2][3], min[2][3];

	scanf("%d", &N);

	for(int i=0;i<N;i++)
	{
		for(int j=0;j<3;j++)
			scanf("%d", &score[i%2][j]);
		if(i==0)
		{
			for(int j=0;j<3;j++)
				max[i][j]=min[i][j]=score[i][j];
			continue;
		}

		max[i%2][0]=score[i%2][0]+(max[(i-1)%2][0]>max[(i-1)%2][1]?max[(i-1)%2][0]:max[(i-1)%2][1]);
		max[i%2][1]=score[i%2][1]+max3(max[(i-1)%2][0],max[(i-1)%2][1],max[(i-1)%2][2]);
		max[i%2][2]=score[i%2][2]+(max[(i-1)%2][1]>max[(i-1)%2][2]?max[(i-1)%2][1]:max[(i-1)%2][2]);

		min[i%2][0]=score[i%2][0]+(min[(i-1)%2][0]<min[(i-1)%2][1]?min[(i-1)%2][0]:min[(i-1)%2][1]);
		min[i%2][1]=score[i%2][1]+min3(min[(i-1)%2][0],min[(i-1)%2][1],min[(i-1)%2][2]);
		min[i%2][2]=score[i%2][2]+(min[(i-1)%2][1]<min[(i-1)%2][2]?min[(i-1)%2][1]:min[(i-1)%2][2]);
	}

	printf("%d %d\n", max3(max[(N-1)%2][0],max[(N-1)%2][1],max[(N-1)%2][2]), min3(min[(N-1)%2][0], min[(N-1)%2][1], min[(N-1)%2][2]));

	return 0;
}