[Gold V] 내려가기 - 2096

문제 링크

성능 요약

메모리: 50812 KB, 시간: 372 ms

분류

다이나믹 프로그래밍, 슬라이딩 윈도우

제출 일자

2024년 7월 4일 23:15:04

문제 설명

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

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

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

입력

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

출력

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

풀이 (DP)

역으로 맨 마지막 구역에서 각각 가장 큰 숫자, 가장 작은 숫자들을 골라가며 올라가고, 가장 처음 구역에서 Math.max 와 Math.min 을 해주면 되는 문제이다.

그림으로 설명해보면...

대충 이런 식으로 표현할 수 있을 것 같다. (그림판에다가 그려서 좀 못 그린게 티가 난다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[][] dp1 = new int[n+1][3]; //최댓값 계산용
		int[][] dp2 = new int[n+1][3]; //최솟값 계산용
		
		for(int i=1; i<=n; i++) { //각각 숫자 입력
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				int num = Integer.parseInt(st.nextToken());
				dp1[i][j]=num;
				dp2[i][j]=num;
			}
		}
		
		for(int i=n; i>=2; i--) {//최댓값 찾기
			dp1[i-1][0] += Math.max(dp1[i][0], dp1[i][1]);
			dp1[i-1][1] += Math.max(dp1[i][0], Math.max(dp1[i][1],dp1[i][2]));
			dp1[i-1][2] += Math.max(dp1[i][1], dp1[i][2]);
		}
		
		for(int i=n; i>=2; i--) {//최솟값 찾기
			dp2[i-1][0] += Math.min(dp2[i][0], dp2[i][1]);
			dp2[i-1][1] += Math.min(dp2[i][0], Math.min(dp2[i][1],dp2[i][2]));
			dp2[i-1][2] += Math.min(dp2[i][1], dp2[i][2]);
		}
		
		int max_num = Math.max(dp1[1][0], Math.max(dp1[1][1], dp1[1][2])); //최댓값 계산
		int min_num = Math.min(dp2[1][0], Math.min(dp2[1][1], dp2[1][2])); //최댓값 계산
		
		System.out.println(max_num +" "+min_num);	
	}
}

[2096 - 내려가기] 위 블로그처럼 2차원 배열이 아닌, 1차원 배열을 이용해 해결하는 방식도 있다.
이 방식도 알아두면 좋을 거 같다.