BAEKJOON / 백준 - JAVA 28450번 컨벤 데드가 하고싶어요

2024.06.21기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 맵의 (0, 0)에서 (h, w)까지 가는데에 가작 적은 숫자의 합으로 간 뒤 재현이의 은신력이랑 비교하여 출력하는 문제입니다.

 

※ 여기서 주의할 점

헬창 형님들의 눈치력 최대치는 1억이며 최대로 있을 수 있는 형님은 1000000이기 때문에 눈치력을 계산하기 위해서는 long타입을 사용해야 가능합니다.

 

예제를 통해서 문제에 대한 풀이를 하도록 하겠습니다.

// 예제
5 5
1 0 2 0 0
0 2 0 0 0
0 0 3 100000000 100000000
0 0 100000000 100000000 100000000
0 0 100000000 100000000 100000000
100000000

 

※ 인덱스의 시작은 (0, 0)으로 작성했습니다.

 

1. 재현이는 아래와 오른쪽으로만 갈 수 있기 때문에, 참조하는 값은 위와, 왼쪽만 가능하다는 걸 알 수 있습니다.

 

2. 우선적으로 입력받은 map에서 h, w가 0일 때에는 참조할 수 있는 값이 위와 왼쪽만 있기 때문에 함수를 통해서 우선적으로 값을 먼저 계산했습니다.

 

h가 0일 때에도 동일하게 작동하여 위쪽 값만 참조합니다.

 

3. 이렇게 준비된 지도를 통해서 (1, 1)부터 (h, w)까지 1번을 활용해 최솟값을 더 해 나갑니다.

그렇게, 바벨이 있는 우측 하단은 300000001값을 가지게 되며, 재현이의 은신력 보다 더 크기 때문에 데드를 못하게됩니다

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static int h, w;
	static long[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		h = Integer.parseInt(st.nextToken()); // 지도의 세로 크기
		w = Integer.parseInt(st.nextToken()); // 지도의 가로 크기
		
		map = new long[h][w]; // 지도
		
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < w; j++) {
				map[i][j] = Long.parseLong(st.nextToken());
			}
		}
		
		int hide = Integer.parseInt(br.readLine()); // 재현이의 은신력
		first();
		
		long min;
		for (int i = 1; i < h; i++) {
			for (int j = 1; j < w; j++) {
				min = Math.min(map[i - 1][j], map[i][j - 1]); // 위, 왼쪽으로 오기 때문에 둘 중에 더 작은 값을 더 해준다.
				map[i][j] += min;
			}
		}
		
		if (map[h - 1][w - 1] > hide) { // 재현이의 은신력보다 눈치력이 높다면
			sb.append("NO");
		} else { // 재현이의 은신력이 더 높다면
			sb.append("YES\n").append(map[h - 1][w - 1]);
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 위, 아래로 밖에 못 움직이기 때문에 h가 0이거나 w가 0일때는 한 쪽으로만 올 수 있다. 
	private static void first() {
		for (int i = 1; i < w; i++) {
			map[0][i] = map[0][i - 1] + map[0][i];
		}
		
		for (int i = 1; i < h; i++) {
			map[i][0] = map[i - 1][0] + map[i][0];
		}
	}
}