백준 - 마인크래프트

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/18111

[문제 설명]

N*M 크기의 맵이 있을 때, 높이를 나라시한다고 했을 때, 최소시간을 구하시오.

최소시간이 여러 개면 가장 높은 높이를 리턴하시오.

 

[접근 방법]

현재 땅의 높이 중 최소 높이부터 최대 높이까지 모든 경우를 만들어보고, 그 중에 시간이 가장 작고, 높이가 가장 높은 것을 리턴한다.

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

위의 테스트 케이스라면 최소 높이가 0 최대 높이가 1이므로, 0부터 1까지 모든 경우의 수를 구한다.

시간 복잡도는 맵을 탐색하는 데 걸리는 시간 M*N(가로*세로)과, 땅의 최소 높이부터 최대 높이까지에 곱이다.

즉, M*N*H(가능한 높이 개수)이다. O(MNH).

조건에서 M,N은 500이하이므로 500*500

땅의 높이는 0~256이므로 257가지 경우의 수

최악의 경우 500*500*257 = 6425만이 된다. 1억회 연산에 1초(1000ms)가 걸린다고 가정하면, 642.5ms에서 오차 범위내.

주어진 시간 제한은 1초(1000ms)이므로 통과가 가능하다.

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

public class Main {
    // 세로 길이
    static int N;
    // 가로 길이
    static int M;
    // 주어진 보드판
    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(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        // 현재 인벤토리에 가지고 있는 블럭 개수
        int cntOfSavedBlock = Integer.parseInt(st.nextToken());
        // 최소 시간을 담을 변수. (최소 시간이므로 최대 시간을 넣어서 초기화)
        int answerTime = Integer.MAX_VALUE;
        // 최대 높이를 담을 변수. (최대 높이를 담을 것이므로 최소 높이를 넣어서 초기화)
        int answerHeight = Integer.MIN_VALUE;

        // 기준이 될 높이들.
        // minHeight부터 maxHeight까지 검사
        int minHeight = Integer.MAX_VALUE;
        int maxHeight = Integer.MIN_VALUE;
        for (int rowIndex = 0; rowIndex < N; rowIndex++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int columnIndex = 0;  columnIndex < M; columnIndex++) {
                int currentHeight = Integer.parseInt(st.nextToken());
                map[rowIndex][columnIndex] = currentHeight;

                minHeight = Math.min(minHeight,currentHeight);
                maxHeight = Math.max(maxHeight,currentHeight);
            }
        }

        for (int height = minHeight; height <= maxHeight; height++) {
            int currentTime = getMinTime(height,cntOfSavedBlock);
            // 만약에 구한 시간이 현재 답보다 작거나 같으면
            if (currentTime <= answerTime) {
                answerTime = currentTime;
                // 구한 높이가 지금까지 구한 높이보다 높으면
                if (answerHeight < height) {
                    answerHeight = height;
                }
            }
        }

        System.out.println(answerTime+" "+answerHeight);
    }

    private static int getMinTime(int targetHeight, int cntOfSavedBlock) {
        int cntOfCurrentBlock = cntOfSavedBlock;
        int time = 0;

        // 만들 높이보다 높은 블록은 제거, 낮은 블록은 추가
        for (int row = 0; row < N; row++) {
            for (int column = 0; column < M; column++) {
                // 현재 높이가 원하는 높이보다 높으므로 블록을 제거하고
                // 인벤토리에 넣고 시간을 추가함.
                if (map[row][column] > targetHeight) {
                    // 여분 블록 개수
                    int cntOfExtraBlock = map[row][column] - targetHeight;
                    // 인벤토리에 넣어줌
                    cntOfCurrentBlock += cntOfExtraBlock;
                    // 시간 추가
                    time += 2*cntOfExtraBlock;
                } else if (map[row][column] < targetHeight) {
                    // 필요한 블록 개수
                    int cntOfNeededBlock = targetHeight - map[row][column];
                    // 인벤토리에서 뺌
                    cntOfCurrentBlock -= cntOfNeededBlock;
                    // 시간추가
                    time += cntOfNeededBlock;
                }
            }
        }

        // 최종적으로 블록개수는 0개 이상이어야함. (인벤토리가 마이너스가 되면 안되니까)
        if (cntOfCurrentBlock >= 0) return time;
        return Integer.MAX_VALUE;
    }
}

 

[참고할 답안]

https://www.acmicpc.net/source/26083829 

로그인

진짜 기가 막힌 답같다. 어차피 결국 어떤 위치에 뭐가 있고는 중요하지 않다.

몇개짜리 블록이 몇개가 있냐가 가장 중요하다.

예를 들어, 1개짜리 블록 7개 2개짜리 블록이 1개면.

1개짜리 블록 7개를 2개로 바꿔주거나 2개짜리 블록을 1개로 바꿔주면 된다.

좌표는 아무 의미가 없다. 진짜 기가 막힌 답안이다.