BOJ 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

 

 

#include <iostream>
#include <stdio.h>
int max_find(int a,int b)
{
	if(a>b) return a;
	return b;
}
int max_find(int a,int b,int c)
{
	int temp = max_find(a,b);
	return max_find(temp,c);
}
int min_find(int a,int b)
{
	if(a<b) return a;
	return b;
}
int min_find(int a,int b,int c)
{
	int temp = min_find(a,b);
	return min_find(temp,c);
}
int main(void)
{
	int N,left,middle,right,sol_max,sol_min;
	int left_max=0;
	int left_min=0;
	int middle_max=0;
	int middle_min=0;
	int right_max=0;
	int right_min=0;
	int left_maxtemp,left_mintemp;
	int middle_maxtemp,middle_mintemp;
	int right_maxtemp,right_mintemp;
	
	scanf("%d",&N);
	for(int i=0;i<N;i++)  //N번반복 
	{
		scanf("%d %d %d",&left,&middle,&right);
		if(i==0) //첫회반복시 max,min 초기화 
		{
			left_max=left; 
			left_min=left;
			middle_max=middle;
			middle_min=middle;
			right_max=right;
			right_min=right;
			continue;
		}
		left_maxtemp=left_max;
		middle_maxtemp=middle_max;
		right_maxtemp=right_max;
		
		left_mintemp=left_min;
		middle_mintemp=middle_min;
		right_mintemp=right_min;
		
		left_max   =  left  + max_find(left_maxtemp,middle_maxtemp);
		middle_max = middle + max_find(left_maxtemp,middle_maxtemp,right_maxtemp);
		right_max  =  right + max_find(middle_maxtemp,right_maxtemp);
		
		left_min   = left   + min_find(left_mintemp,middle_mintemp);
		middle_min = middle + min_find(left_mintemp,middle_mintemp,right_mintemp);
		right_min  = right  + min_find(middle_mintemp,right_mintemp);	
	}
	
	sol_max=max_find(left_max,middle_max,right_max);
	sol_min=min_find(left_min,middle_min,right_min);
	
	printf("%d %d\n",sol_max,sol_min);
}