[백준/JAVA] 2096_내려가기

백준🔗

2096번: 내려가기

 

문제

 

 

 

간단 풀이

처음에는 DFS인가 했는데 시간초과가 발생했다! 문제를 다시 읽으며 생각해보니 N이 최대 100000이기 때문에 줄을 이동할 때마다 최대 3개의 경우씩 100000줄이면 3^100000의 시간 복잡도 되는건가.. 

암튼 그래서 DFS가 아닌 DP로 방법을 수정했다.

 

주어진 문제 상황에서 각 줄로 이동할 때의 선택은 이전 줄에 대해서만 영향을 받기 때문에 dp 배열은 N*3의 2차원 배열이 아닌 1차원 배열로 만들었다.  

이전 줄의 (왼쪽), 위, (오른쪽) 중에서 최대 or 최소값에 현재 위치의 값을 더해가면서 최종적으로 최대 or 최소 점수를 구할 수 있도록 했다.  

 

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][3];
		int[] dp_max = new int[3];
		int[] dp_min = new int[3];
		int zero, one, two;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			map[i][0] = st.nextToken().charAt(0) - '0';
			map[i][1] = st.nextToken().charAt(0) - '0';
			map[i][2] = st.nextToken().charAt(0) - '0';
			if (i == 0) {
				dp_max[0] = dp_min[0] = map[i][0];
				dp_max[1] = dp_min[1] = map[i][1];
				dp_max[2] = dp_min[2] = map[i][2];
				continue;
			}
			// 최대
			zero = Math.max(dp_max[0], dp_max[1]) + map[i][0];
			one = Math.max(dp_max[0], Math.max(dp_max[1], dp_max[2])) + map[i][1];
			two = Math.max(dp_max[1], dp_max[2]) + map[i][2];
			dp_max[0] = zero;
			dp_max[1] = one;
			dp_max[2] = two;
			// 최소
			zero = Math.min(dp_min[0], dp_min[1]) + map[i][0];
			one = Math.min(dp_min[0], Math.min(dp_min[1], dp_min[2])) + map[i][1];
			two = Math.min(dp_min[1], dp_min[2]) + map[i][2];
			dp_min[0] = zero;
			dp_min[1] = one;
			dp_min[2] = two;
		}

		int max = Math.max(dp_max[0], Math.max(dp_max[1], dp_max[2]));
		int min = Math.min(dp_min[0], Math.min(dp_min[1], dp_min[2]));
		System.out.println(max + " " + min);
	}
}

 

 

참고 자료