문제 url:
마인크래프트
문제:
🤔 문제 알아보기
쉽지 않은 난이도의 문제이다. 먼저, 해당 문제를 브루트포스를 생각했는가에 따라 문제 난이도가 확 달라질 것 같다.
그럼 해당 문제가 왜 브루트포스가 가능한지를 알아보자!
먼저, 가로 M 세로 N을 입력받는데, 해당 값은 1<= M,N <= 500의 범위를 가진다고 한다.
그럼, 총 250,000 연산 횟수로 모든 배열을 훑어보기에는 충분하다.
하지만, 문제를 잘 읽어보면 땅 고르기 작업에 걸리는 최소시간을 계산한 후 그 경우 땅의 높이를 출력 해야한다.,
즉, 입력받은 배열에서 어떤 높이로 땅 고르기를 해야 시간이 제일 적게 나오는지를 판단해야 하기 때문에 모든 높이를 계산할 필요가 있다.
여기서 높이는 0<= h <= 256을 가진다고 한다. 그러면 총 257번을 반복할 수 있어야 하는데,
그럼 500 * 500 * 257의 값이 1억이하의(보통 시간 제한 1초 시 1억번 연산횟수를 가짐) 값을 가져야 브루트포스 알고리즘으로 구현할 수 있다는 얘기이다.
계산기에 계산해보니깐, 64,250,000으로 다행히 1억번 이하의 반복횟수를 가진다.
자 그럼! 왜 브루트포스 알고리즘으로 문제를 구현할 수 있는지 확인했으니 문제 조건을 알아보자
문제 조건
- 하나의 높이로 땅 고르기를 실시한다. 즉, 높이가 50, 62, 63이 존재한다면, 세 높이 중 하나로 높이를 맞춘다는 얘기
- 땅을 캐면(높이를 낮추면) 2초의 시간이 걸리고 블록 한 개를 얻는다.
땅을 쌓으면(높이를 높이면) 1초의 시간이 걸리고 블록 한 개를 잃는다.- ※중요 : 최소시간이 같을 경우 높이가 높은 땅을 출력한다.
- 블록이 존재하지 않으면, 땅을 쌓을 수 없기 때문에 땅을 캐야 한다. TC 3을 참조
자 그럼 이제 코드와 함께 문제 조건을 풀어보자.
🐱👤 실제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int[][] land = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
int value = Integer.parseInt(st.nextToken());
if(value > max) {
max = value;
}
else if(value < min) {
min = value;
}
land[i][j] = value;
}
}
int res_sec = Integer.MAX_VALUE;
int res_height = 0;
for(int k = min; k <= max; k++) {
int sec = 0;
int inventory = B;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int diff = land[i][j] - k;
/*
* 0보다 크다는 얘기는 현재 높이가, 가장 낮은 값보다 크다는 얘기
* 즉, 땅을 파야한다는 얘기이다.
*/
if(diff > 0) {
sec += 2 * diff;
inventory += diff;
}
else if(diff < 0) {
sec += -diff;
inventory += diff;
}
}
}
if(inventory < 0) {
continue;
}
if(res_sec >= sec) {
res_sec = sec;
res_height = Math.max(res_height,k);
}
}
System.out.println(res_sec + " " + res_height);
}
}😎 코드 풀이 및 해석
1번 째 코드
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int[][] land = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
int value = Integer.parseInt(st.nextToken());
if(value > max) {
max = value;
}
else if(value < min) {
min = value;
}
land[i][j] = value;
}
}
land 2차원 배열은 입력 조건에 맞게 선언하였으며,
추후 2번 째 코드에서 현재 존재하는 모든 높이를 고려하기 위해 땅의 높이중 가장 높은 max, 가장 낮은 min변수를 정의
굳이 Integer.MAX_VALUE 혹은 MIN_VALUE할 필요 없이
max는 -1, min은 257을 줘도 무방하다.
높이는 0<= h <= 256까지의 범위를 가지기 때문2번 째 코드
int res_sec = Integer.MAX_VALUE;
int res_height = 0;
for(int k = min; k <= max; k++) {
int sec = 0;
int inventory = B;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int diff = land[i][j] - k;
/*
* 0보다 크다는 얘기는 현재 높이가, 가장 낮은 값보다 크다는 얘기
* 즉, 땅을 파야한다는 얘기이다.
*/
if(diff > 0) {
sec += 2 * diff;
inventory += diff;
}
else if(diff < 0) {
// 0보다 작기 때문에 음수이다.
// 하지만 초는 음수가 되면 안되기에 -를 붙인 것
sec += -diff;
inventory += diff;
}
}
}
if(inventory < 0) {
continue;
}
if(res_sec >= sec) {
res_sec = sec;
res_height = Math.max(res_height,k);
}
}먼저 변수부터 설명하겠다.
int res_sec = Integer.MAX_VALUE;
int res_height = 0;
int sec = 0;
int inventory = B;res_sec은 최소시간을 입력받기 위한 변수이며, res_height는 해당 높이를 입력받기 위한 변수이다.
여기서 res_sec은 특별한 경우가 아니라면 Integer.MAX_VALUE로 하는것이 좋다.
필자는 버릇처럼 최대 크기값을 주어 불필요한 경우의 수를 줄이는 편인데,
나중에 타 블로그 글들을 정독하면서 최대시간이 50253 정도 된다고 한다.
마인크래프트 최대 시간
이를 처음부터 알고 풀 사람들은 없으니 속 편하게 MAX_VALUE로 가겠다.
sec변수는 반복문안에서 시간을 입력받기 위한 변수로, 반복문이 돌 때마다 0으로 초기화 된다는 점을 기억해줘야 한다.
마지막으로 inventory는 현재 가진 블록의 개수로,
위에서 설명했던 조건과 같이 블록이 없는데 블록을 쌓을 수 없다.
그런데! 만약 블록을 쌓게 되면 음수가 나오는 데, 이는 나중에 코드와 함께 다시 설명하겠다.
for(int k = min; k <= max; k++) {
int sec = 0;
int inventory = B;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int diff = land[i][j] - k;
/*
* 0보다 크다는 얘기는 현재 높이가, 가장 낮은 값보다 크다는 얘기
* 즉, 땅을 파야한다는 얘기이다.
*/
if(diff > 0) {
sec += 2 * diff;
inventory += diff;
}
else if(diff < 0) {
sec += -diff;
inventory += diff;
}
}
}
반복문에 대한 로직이다.
모든 배열을 확인하기 위한 이중 for문이 아래에 위치하고,
높이를 반복하는 반복문은 현재 입력받은 높이를 모두 확인해야 하기 때문에 최상단에 위치한다.
우리는 최상단 반복문을 통해 min과 max변수를 왜 입력받는지 이해가 됐을 것이다.
자, 이제 같이 배열을 확인하는 이중 for문을 확인해보자,
현재 배열의 값이 높이(k)보다 크다면 현재 위치가 높기 때문에 땅을 파야한다.
즉, 0보다 큰 상황이기 때문에 최소시간을 +2초를 해주고, 판만큼 블록을 더해준다.
만약 현재 높이와 배열 높이가 같다면 0이 되기 때문에 어떤 조건문도 동작하지 않는다.
그럼 배열의 값이 높이(k)보다 작다면 높이를 높여야 하기 때문에 inventory에서 블록을 꺼내 쌓아야 한다.
그래서 1초의 시간이 걸리며 높이만큼 블록을 잃게 되는 것이다.
여기서 트러블 슈팅 하나!
// 트러블 슈팅 if(diff > 0) { sec += 2; inventory++; } else if(diff < 0) { sec++; inventory--; }필자는 처음에 이렇게 코드를 짰다. 필자와 같은 실수를 하시는 분이 혹시나 계실 수 있어 이렇게 트러블 슈팅을 했는데,
우리는 높이만큼 쌓거나 파야 하기 때문에 단순히 초를 더하는 것이 아닌
높이의 차이만큼 초를 더해아 하는 것이다. 그래서 이렇게 접근하면 안되는 것!
if(inventory < 0) {
continue;
}
if(res_sec >= sec) {
res_sec = sec;
res_height = Math.max(res_height,k);
}마지막 로직이다. 해당 로직은 현재 최상단 반복문안에 속해 있음을 복기한 후 설명하겠다.
먼저 위에서 설명했듯, inventory에 블록이 없는데 땅을 쌓게 되면 반드시 inventory는 음수가 될 것이다. 이는 조건이 맞지 않기 때문에
아래의 로직을 동작하지 않고 다시 반복문을 돌기 위해 continue를 진행
그런 다음, 최소시간을 구하기 위해 현재 시간과 결과 시간을 비교한 후
작거나 같으면 현재 시간을 입력한다.
그리고 만약 최소시간이 같다면 땅의 높이가 가장 높은 값을 저장해야 하는데
이를 위해 Math.max를 이용해 최대값을 비교한 후 초기화 시키는 로직이다.
💜 회고
해당 문제는 생각보다 정답 비율이 낮은 문제로 쉽지 않았다.
브루트포스가 아닌 다른 방식이 존재하는 지는 모르겠지만, 아직까지는 브루트 포스 조차 쉽게 구현하는 정도가 아니라서 다른 방식을 잘 모르겠다.
최근 브루트포스 문제를 풀지 않았는데, 시간의 여유가 좀 있으면 문제 편식을 하지 않고 다양하게 풀어보도록 해보긴 해야겠다.
