문제
https://www.acmicpc.net/problem/18111
문제 접근
처음에 어떻게 구현해야 할지 많이 막막했다... 그나마 생각난 게 일일이 브루트포스로 돌리면서 푸는 것이였는데, 일일이 풀기엔 시간이 1초밖에 주어지지 않아서 틀릴 것이라고 생각했다.
그래서 다른 분의 글을 조금 참고해보았는데,
출처 : https://wonit.tistory.com/540
입력에 들어오는 값들을 보면
배열이 500 * 500 크기까지 존재할 수 있고,
B에는 최대 6억4천개의 블록이 존재할 수 있다.
이런 경우 최악의 경우 n^3이 1천만 정도가 되어서 브루트 포스 알고리즘을 이용해서 풀 수 있다고 한다.
(근데 실은 잘 이해가 되지 않아서... 질문 게시판에 여쭤보고 추가로 남기겠다.)
한 고수 분의 답변을 통해... 이 문제의 시간 복잡도가 아래와 같이
N x M개의 배열을 모두 탐색하면서 땅의 높이를 0~255까지 진행하며 확인하는... 이런 시간복잡도가 나온다는 것을 알게 되었다.
N x M 은 최대 500 * 500 = 25000까지 가능하므로...
500 x 500 x 256 <= 10^8(1억) 이다.
https://velog.io/@dbtlwns/%EC%B7%A8%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B2%BD%ED%97%98%EA%B3%B5%EC%9C%A0
잘 몰라서 찾아보니까 위의 글에서
대략 10^8(1억) 번의 반복문을 1초로 근사하게 계산한다고 한다. 따라서 브루트포스로 풀어도 1초의 시간 제한 안에 해결할 수 있는 것이다. 고수님 감사합니다..!!
이를 토대로 입력받은 땅 높이들 중 가장 낮은 높이부터 가장 높은 높이까지 한 높이씩 확인해보면서, 해당 높이로 만들기 위해 필요한 시간을 계산하여 갱신하는 방식으로 진행하였다.
하지만 1%에서 바로 틀렸다고 떴다.
질문게시판에 반례 모음을 올리신 분이 계셔서 이 분 덕분에 반례들을 넣어보며 내 코드의 문제점을 확인할 수 있었다.
https://www.acmicpc.net/board/view/86190
각 높이 별로 확인할 때 temp_b 변수를 두어 인벤토리 속 블록 개수가 0보다 적은지 판단하며 진행했는데, 모든 블록들을 진행한 후에 판단했어야 했는데 진행하는 도중에 판단을 해버렸던 것이 문제였다. 그래서 수정했다.
그리고, 이렇게 고쳤음에도 불구하고 계속 틀렸습니다가 떴는데, 내가 당시에 min_time을 1000으로만 잡았었던 것이 문제였다. 임시로 10억으로 매우 큰 수로 초기화했더니 맞았습니다가 떴다. 하지만 이건 너무 불필요하게 큰 값이고...
https://www.acmicpc.net/board/view/97184
이 글을 확인해보면 최소 시간의 최댓값이 50253라고 한다!
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
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());
Integer n = Integer.parseInt(st.nextToken());
Integer m = Integer.parseInt(st.nextToken());
Integer b = Integer.parseInt(st.nextToken());
int[][] ground = 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++) {
ground[i][j] = Integer.parseInt(st.nextToken());
if (ground[i][j] < min) {
min = ground[i][j];
}
if (ground[i][j] > max) {
max = ground[i][j];
}
}
}
int min_time = 1000000000;
int max_height = 0;
Loop1:
for (int height = min; height <= max; height++) {
int del_count = 0;
int ins_count = 0;
int temp_b = b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (ground[i][j] < height) {
ins_count += height - ground[i][j];
temp_b -= height - ground[i][j];
} else if (ground[i][j] > height) {
del_count += ground[i][j] - height;
temp_b += ground[i][j] - height;
}
}
}
if (temp_b < 0) {
continue Loop1;
}
int time = del_count * 2 + ins_count;
if (time <= min_time && height >= max_height) {
min_time = time;
max_height = height;
}
}
System.out.println(min_time + " " + max_height);
}
}