BOJ_S2_18111

📁 [S2_18111] 마인크래프트

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

public class Main {
	static int N, M, B;
	static int max_floor, min_floor;
	static int time, height;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// **** input start ****

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		map = new int[N][M];

		max_floor = Integer.MIN_VALUE;
		min_floor = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				// 최대층 최소층 구하기
				max_floor = Math.max(max_floor, map[i][j]);
				min_floor = Math.min(min_floor, map[i][j]);
			}
		}

		// **** input end ****

		// 층마다 체크
		check();

		System.out.println(time + " " + height);

	} // main end

	// 층을 기준으로 체크
	static void check() {
		// 결과 시간
		time = Integer.MAX_VALUE;
		// 결과 층
		height = -1;

		for (int i = min_floor; i <= max_floor; i++) {
			// 인벤토리
			int invent = B;
			// 체크하는 시간
			int second = 0;

			for(int j=0; j<N; j++) {
				for(int z=0; z<M; z++) {
					// 좌표와 층 차이
					int minus = map[j][z] - i;

					// 좌표가 더 큰 경우 1번 실행
					if(minus > 0) {
						// 시간 추가
						second += (Math.abs(minus)*2);
						// 인벤 추가
						invent += Math.abs(minus);
					}
					// 좌표가 더 작은 경우 2번 실행
					else if(minus < 0) {
						// 시간 추가
						second += Math.abs(minus);
						// 인벤 빼기
						invent -= Math.abs(minus);
					}
				}
			}
			// 조건 부합
			if(invent >= 0) {
				// 가장 짧은 시간인 경우
				if(second <= time) {
					// 시간, 층 갱신
					time = second;
					height = i;
				}
			}
		}
	}
} // class end

🤔 나의 생각

처음엔 완탐으로 모든 좌표를 기준으로 모든 경우를 계산해서 최소인 시간을 선택하려 했으나.. 시간 복잡도가 초과하는 것을 알면서도 가지치기를 잘하면 되겠지라는 생각을 가졌다…
큰 오 산 이 였 다 .. ㅎ
그래서 빠르게 다 지우고 다시 생각을 해보니
비슷한 방법이지만 큰 기준을 map의 좌표가 아닌 층으로 기준을 잡고하면 3중 for문인데 그것도 층의 높이는 최대 256이라 시간 복잡도의 둘레에서 벗어날 수 있었다.

과정은 다음과 같다.

• 좌표의 최대 층과 최소 층을 구해 모든 층(i)에서 확인한다.
• 만약 좌표가 i 보다 클 경우 1번 작업을 실행한다.
• 만약 좌표가 i 보다 작을 경우 2번 작업을 실행한다.
• 인벤이 0보다 작을경우는 통과 ( 조건에 어긋난다 )
• i 마다 시간과 결과 층을 구해 시간이 줄어들때마다 갱신을 해준다.