[백준/BOJ] 18111번 : 마인크래프트 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

18111번: 마인크래프트

---

- 문제 -

 

난이도 실버 2 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

땅을 평평하게 만들어줘야한다. 블록을 제거하던가, 블록을 추가해서.

좌표들 중 최솟값과 최댓값을 구해준다. 구했으면 이제 모든 경우의 수는 최솟값~최댓값에서 나올 수 있다.

최댓값 - 최솟값 만큼 반복하는 반복문을 만든다.

최솟값이 3, 최댓값이 10이면 3~10까지가 땅의 높이가 되는 것이고, 10도 포함해야하니 총 8가지의 경우의 수가 나올 것이다. 땅의 높이를 3~ 10으로 맞춰가면서, 걸린 시간과 블록의 개수를 체크해준다. 땅을 평평하게 만들었을때 시간이 이전 땅의 높이를 만들었을때보다 적게 들었다면 시간과 현재 땅의 높이를 저장한다. 땅의 높이가 같다면 땅의 높이가 더 높은 값을 저장한다. 그리고 블록의 개수를 체크했었다. 이유는 지금 땅을 평평하게 만들었는데 사용된 블록이 음수이면 그 땅을 만들 수가 없다는 것이고, 블록이 0이상이면 땅을 평평하게 만들 수 있다는 것이다.

 

예를 들어보자.

2 2 2

5 1

2 5

을 입력받았다. 그렇다면 좌표는 5 1 / 2 5이고, 이 중 최솟값은 1, 최댓값은 5이다.

땅의 높이는 1~5까지 만들 수 있다는 것이다.

 

땅의 높이를 1로 만들어보자.

5 > 1로 만들면 얻는 블록의 수는 4개이고, 걸리는 시간은 8이다.(블록을 제거할때는 2배의 시간이 든다.)

1은 그대로니 패스.

2 > 1로 만들면 얻는 블록의 수는 1개이고, 걸리는 시간은 2이다.

5 > 1로 만들면 4개의 블록과 8의 시간.

총 시간은 17이고, 높이는 1. 블록은 11개 양수이니 조건에 맞다.

 

다음 높이를 보자.

5 > 2 는 블록 3, 시간 6.

1 > 2 는 블록 -1, 시간 1.

5 > 2 는 블록 3, 시간 6.

총 시간은 13, 높이는 2, 블록 7개 양수. 조건에 맞고, 1층보다 시간이 적게드니 13과 2를 저장한다.

 

다음 높이

5 > 3은 블록 2, 시간 4.

1 > 3은 블록 -2, 시간 2.

2 > 3은 블록 -1, 시간 1.

5 > 3은 블록 2, 시간 4.

총 시간은 11, 높이는 3, 블록은 3개 양수. 조건에 맞고, 2층보다 시간이 적게드니 11과 3을 저장.

 

다음

5 > 4 블록 1, 시간 2.

1 > 4 블록 -3, 시간 3.

2 > 4 블록 -2, 시간 2.

5 > 4 블록 1, 시간 2.

총 시간 9, 높이는 4, 블록은 -1 음수. 3층보다 시간은 적게들었지만, 블록이 부족하니 조건에 맞지 않아 저장X.

 

다음

5층이니 5는 패스.

1 > 5 블록 -4, 시간 4.

2 > 5 블록 -3, 시간 3.

총 시간 7, 높이는 5, 블록은 -5 음수. 4층과 동일한 상황. 조건에 맞지 않으니 저장하지 않는다.

 

필자가 적어둔 예제를 보면 알 수 있듯이. 층이 높아질 수록 시간과, 블록의 개수는 낮아지고, 높이는 높아진다.

이렇다면 위 행동을 반복할때, 블록이 0보다 낮아지기 전까지 계속 시간과 층을 저장하면, 제일 높은 층과 제일 낮은 

저장 될 것이고, 블록이 음수가 되었을때 반복문을 종료하면 원하는 출력값을 얻을 수  있다.

 

주의할 점은 필자도 단순한거지만 간과해서 여러번 틀린 부분인데.

최소 시간이 올 수 있는 최댓값을 처음엔 1000을 잡았다... 크게 생각 못한 부분인걸 인정한다.

필자가 얼추 계산해봤을때 올 수 있는 최댓값은 6400만인것 같고, 넉넉 잡아 9999만으로 잡아줬다.

이것만 주의하면 크게 문제 될 건 없는 문제이다.

 

코드를 보자.

---

-풀이-

 

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 = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][M];
		int min = 256;
		int max = 0;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(min > arr[i][j]) min = arr[i][j];
				if(max < arr[i][j]) max = arr[i][j];
			}
		}
		
		//time은 최소시간을 저장 할 변수, 풀이에 적었듯이 
		//올 수 있는 값은 6400만정도로 예상 되기에 넉넉히 9999만을 저장.
		int time = 99999999;
		int high = 0;
		//만틀 층 i
		for(int i = min; i <= max; i++) {
			int count = 0;
			int block = B;
			//좌표 j와 k
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < M; k++) {
					//현재 좌표의 층이 만들 층보다 높으면 제거하는데, 블록은 제거한 만큼 추가, 시간은 두배로
					if(i < arr[j][k]) {
						count += ((arr[j][k] - i) * 2);
						block += (arr[j][k] - i);
					//낮을 경우 블록은 제거, 시간은 1배
					}else {
						count += (i - arr[j][k]);
						block -= (i - arr[j][k]);
					}
				}
			}
			//블록의 개수가 음수가 되면 반복문 종료
			if(block < 0) break;
			
			if(time >= count) {
				time = count;
				high = i;
			}
		}
		System.out.println(time + " " + high);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.