백준 2096 내려가기(자바)

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

2096번: 내려가기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

4 MB (하단 참고)

32854

12480

9700

36.561%

문제

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

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

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

입력

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

출력

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

---

이 문제는 DP를 이용한 문제이다.

MAX와 MIN을 구해야 하는 문제이므로 (N, 3)의 크기를 가지는 MAX와 MIN배열을 만들어서 구하려고 했으나

DP의 특징인 '시간은 줄이지만 메모리를 많이 먹는다'를 다시 한 번 깨닫게 해주는 문제였다.

 

이 문제를 풀기 위해서는 슬라이딩 윈도우 기법을 활용해야 한다.

(2,3)배열을 생성해서 처음에 1행의 값을 넣어준다.

이후 2행에 MAX or MIN의 값을 넣어주고 2행의 값을 1행으로 덮어씌운다.

초라한 사진이지만 왼쪽처럼 1,2,3으로 6,8,9라는 값을 구해서 2행에 저장했으면

바로 2행의 값을 다시 1행에 덮어씌운다. 그리고 1행의 값으로 다시 MAX or MIN을 구해서 2행에 넣고 반복하는 방법이다.

 

이러면 최대, 최소를 구하는 로직만 만들면 짧은 배열을 이용해서 메모리를 아껴서 구할 수 있다.

 

우선 전체 코드를 살펴보자.

import java.util.Arrays;
import java.util.Scanner;

public class baek_2096_내려가기_골드5 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] map = new int[N][3];
		for(int i=0; i<N; i++) {
			map[i][0] = sc.nextInt();
			map[i][1] = sc.nextInt();
			map[i][2] = sc.nextInt();
		}
		
		int[][] maxDP = new int[2][3];
		int[][] minDP = new int[2][3];
		
		maxDP[0][0] = map[0][0];
		maxDP[0][1] = map[0][1];
		maxDP[0][2] = map[0][2];
		minDP[0][0] = map[0][0];
		minDP[0][1] = map[0][1];
		minDP[0][2] = map[0][2];
		
		for(int i=1; i<N; i++) {
			maxDP[1][0] = Math.max(maxDP[0][0], maxDP[0][1])+map[i][0]; 
			maxDP[1][1] = Math.max(maxDP[0][0], Math.max(maxDP[0][1], maxDP[0][2]))+map[i][1];
			maxDP[1][2] = Math.max(maxDP[0][1], maxDP[0][2])+map[i][2];
			maxDP[0][0] = maxDP[1][0];
			maxDP[0][1] = maxDP[1][1];
			maxDP[0][2] = maxDP[1][2];
		}
		
		for(int i=1; i<N; i++) {
			minDP[1][0] = Math.min(minDP[0][0], minDP[0][1])+map[i][0]; 
			minDP[1][1] = Math.min(minDP[0][0], Math.min(minDP[0][1], minDP[0][2]))+map[i][1];
			minDP[1][2] = Math.min(minDP[0][1], minDP[0][2])+map[i][2];
			minDP[0][0] = minDP[1][0];
			minDP[0][1] = minDP[1][1];
			minDP[0][2] = minDP[1][2];
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=0; i<3; i++) {
			if(max<maxDP[0][i]) max = maxDP[0][i];
		}
		int min = Integer.MAX_VALUE;
		for(int i=0; i<3; i++) {
			if(min>minDP[0][i]) min = minDP[0][i];
		}
		System.out.println(max+" "+min);
	}
}

DP를 처음 접하기도 했어서 아직 코드가 정리가 안 된 상태이다.

 

public class baek_2096_내려가기_골드5 {                   
	public static void main(String[] args) {        
		Scanner sc = new Scanner(System.in);        
		int N = sc.nextInt();                       
		int[][] map = new int[N][3];                
		for(int i=0; i<N; i++) {                    
			map[i][0] = sc.nextInt();               
			map[i][1] = sc.nextInt();               
			map[i][2] = sc.nextInt();               
		}                                           
		                                            
		int[][] maxDP = new int[2][3];              
		int[][] minDP = new int[2][3];              
		                                            
		maxDP[0][0] = map[0][0];                    
		maxDP[0][1] = map[0][1];                    
		maxDP[0][2] = map[0][2];                    
		minDP[0][0] = map[0][0];                    
		minDP[0][1] = map[0][1];                    
		minDP[0][2] = map[0][2];

우선 (N,3)의 크기를 가지는 map을 하나 만들어서 전체의 값을 입력 받았다.

슬라이딩 윈도우를 사용하기 위해 maxDP랑 minDP를 만들었다.

그리고 1행에는 map의 1행의 값을 전부 집어넣어주었다.

 

for(int i=1; i<N; i++) {                                                                     
	maxDP[1][0] = Math.max(maxDP[0][0], maxDP[0][1])+map[i][0];                              
	maxDP[1][1] = Math.max(maxDP[0][0], Math.max(maxDP[0][1], maxDP[0][2]))+map[i][1];       
	maxDP[1][2] = Math.max(maxDP[0][1], maxDP[0][2])+map[i][2];                              
	maxDP[0][0] = maxDP[1][0];                                                               
	maxDP[0][1] = maxDP[1][1];                                                               
	maxDP[0][2] = maxDP[1][2];                                                               
}

max의 값을 구하는 로직이다.

0번 열에는 이전 값에서 0번과 1번의 값만 비교해서 map에 더해주면 된다.

1번 열에는 이전 값에서 0번, 1번, 2번 값을 비교해서 map에 더해주면 된다.

2번 열에는 이전 값에서 1번, 2번 값을 비교해서 map에 더해주면 된다.

다 구했으면 maxDP의 1행의 값을 0행으로 다시 덮어씌워준다.

 

for(int i=1; i<N; i++) {                                                                       
	minDP[1][0] = Math.min(minDP[0][0], minDP[0][1])+map[i][0];                                
	minDP[1][1] = Math.min(minDP[0][0], Math.min(minDP[0][1], minDP[0][2]))+map[i][1];         
	minDP[1][2] = Math.min(minDP[0][1], minDP[0][2])+map[i][2];                                
	minDP[0][0] = minDP[1][0];                                                                 
	minDP[0][1] = minDP[1][1];                                                                 
	minDP[0][2] = minDP[1][2];                                                                 
}

동일하게 min의 값을 구하는 로직이다.

 

int max = Integer.MIN_VALUE;                                                                         
for(int i=0; i<3; i++) {                                                                             
	if(max<maxDP[0][i]) max = maxDP[0][i];                                                           
}                                                                                                    
int min = Integer.MAX_VALUE;                                                                         
for(int i=0; i<3; i++) {                                                                             
	if(min>minDP[0][i]) min = minDP[0][i];                                                           
}                                                                                                    
System.out.println(max+" "+min);

다 구했으면 max랑 min이라는 변수를 생성해서 maxDP, minDP의 0 or 1행의 값에서 최대, 최소를 구해주면 된다.

 

예제 코드를 넣어서 maxDP, minDP를 뽑아냈다.

1행의 값을 0행에 덮어씌우고 종료했으므로 0번 행과, 1번 행의 값은 같게 나온다.

12, 18, 9에서 최대인 18 

9, 14, 6에서 최소인 6을 출력하면 정답이 된다.