[백준] no18111: 마인크래프트

문제

N : 입력한 땅의 세로 길이

M : 입력한 땅의 가로 길이

B : 처음에 가진 여분의 블록수

조건 1: 블록을 치우면, 시간은 블록당 2초 걸리며, 치운 블록은 B와 함께 인벤토리에 넣음

조건 2: 블록을 채우면, 시간은 블록당 1초 걸리며, 채울 블록이 없으면 아래층으로 가야함

 

문제 링크 : https://www.acmicpc.net/problem/18111

---

원리

: 브루트 포스 (최상층에서부터 반복해야 연산 수가 적다)

---

풀이방법

1. 같은 층에 블록 개수가 제일 많은 층을 구하고, 그 층을 기준으로 계산하는 방법 [실패]

/**
 * 0. 0<i<N, 0<j<M으로 순회하여 매트릭스 생성
 * 1. 매트릭스 내에서 같은 숫자가 가장 많은 수를 찾음 => HashMap을 이용한 count (밸류값이 갯수)
 * 2. 가장 많은 수 = maxVal
 * 3. 매트릭스를 순회하며, maxVal - a[i][j] 해서, 값이 음수면 removeWork += 해당 값   = 제거해야할 불록은 -
 * 4. 매트릭스를 순회하며, maxVal - a[i][j] 해서, 값이 양수면 addWork += 해당 값   = 모자란 블록은 +
 * 5. 만약 removeWork의 절대값 + B(여분) < addWork 이면, removeWork의 절대값 + 현재 max층의 블록개수 => max층도 -1
 * 6. N*N - (max-1층의 블록수)만큼을 이제 안채워도 되므로, addBlck - 해당 블록수를 addBlck으로 세팅
 * 7. removeTime = removeWork * 2초
 * 8. addTime = addWork * 1초
 * 9. workTime = removeTime + addTime;
 */

 

2. 브루트포스

: 최상층부터 순차적으로 구하는 방법. 블록 계산 후 최종 시간 계산

 

3. 브루트포스 

: 최상층부터 순차적으로 구하는 방법. 시간 계산하며 비교

: 면적에 대해 자료구조로 처리

* 기준시간을 문제의 조건에 맞게 계산 필요

* 반복조건에서 0층에 대한 산정 필요

---

나의 코드

1. 실패

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[][] rand = new int [N][M];
    Map<Integer, Integer> maxCheck = new HashMap<>();

    for(int i=0; i<N ; i++) {
        StringTokenizer stNum = new StringTokenizer(br.readLine(), " ");
        for(int j=0;j<M;j++) {
            int block = Integer.parseInt(stNum.nextToken());
            rand[i][j] = block;
            if (maxCheck.containsKey(block)) maxCheck.put(block, maxCheck.get(block) + 1);
            else maxCheck.put(block, 1);
        }
    }

    int maxVal = Collections.max(maxCheck.values());
    int max = getMaxValue(maxVal, maxCheck);

    int removeBlock = 0;
    int addBlock = 0;
    for(int i=0; i<N ; i++) {
        for(int j=0;j<M; j++) {
            if ((max-rand[i][j])<0) removeBlock += (rand[i][j] - max);
            else if ((max-rand[i][j])>0) addBlock += (max - rand[i][j]);
        }
    }

    if(removeBlock + B < addBlock) {
        removeBlock += maxVal;
        max--;
        int cnt=0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) if (rand[i][j] == max) cnt++;
        }
        addBlock -= ((N*M) - cnt);
    }

    System.out.println((removeBlock * 2) + (addBlock * 1)+ " " + max);
}

private static int getMaxValue(int maxVal, Map<Integer, Integer> maxCheck) {
    List<Integer> keyList = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : maxCheck.entrySet()) {
        if (entry.getValue().equals(maxVal)) {
            keyList.add(entry.getKey());
        }
    }
    Collections.sort(keyList, Collections.reverseOrder());
    return keyList.get(0);
}

 

2. 브루트 포스 [실패]

public class no18111 {

    private static int max;
    private static int time;

    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());

        max = 0;
        List<Integer> rand = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer tempSt = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int block = Integer.parseInt(tempSt.nextToken());
                rand.add(block);
                if (block > max) max = block;
            }
        }
        blockCount(rand, N, M, B);

        System.out.println("" + time + " " + max);
    }

    private static void blockCount(List<Integer> rand, int N, int M, int B) {
        int remove = 0; // * 2sec
        int add = 0;  // * 1sec
        for (int i = 0; i < N*M; i++) {
            if (rand.get(i) > max) remove += (rand.get(i) - max);
            else if (rand.get(i) < max) add += (max - rand.get(i));
        }

        // 아래층
        int remove2 = 0;
        int add2 = 0;
        for (int i = 0; i < N*M; i++) {
            if (rand.get(i) > (max-1)) remove2 += (rand.get(i) - (max-1));
            else if (rand.get(i) < (max-1)) add2 += ((max-1) - rand.get(i));
        }

        if(((Math.abs(remove) * 2) + add) > ((Math.abs(remove2) * 2) + add2)) {
            remove = Math.abs(remove2);
            add = add2;
            max--;
        }

        if (remove + B < add) {
            max--;
            blockCount(rand, N, M, B);
        } else time = (Math.abs(remove) * 2) + add;
    }
}

 

3. 브루트 포스 [성공]

: 결국 문제는 0층을 계산 안했다는 것과, 최대 시간을 계산해서 넣지 않고 임의로 넣어서 발생했다.

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class no18111 {

    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());

        /**
         * 입력받은 대로 꼭 매트릭스일 필요가 없다.
         * 어차피 모든 위치의 블록수를 계산하기 때문에 자료구조로 일렬로 나열해도 된다.
         */
        List<Integer> rand = new ArrayList<>();
        for(int i=0; i<N ; i++) {
            StringTokenizer randSt = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<M ; j++) {
                rand.add(Integer.valueOf(randSt.nextToken()));
            }
        }

        /**
         * 최대 높이를 구해서 한 층씩 내려갈 것임. 위에서부터 내려오는게 연산이 더 적다.
         */
        int floor = rand.stream().mapToInt(a->a).max().getAsInt();

        /**
         * 땅의 넓이 = N*M이며, N과 M은 최대 500이므로, 2500를 초과할 수 없다. 또한, 치우는 시간이 더 크므로, 최대 블록수*2를 초과할 수 없다
         * 따라서, 500 * 500 * 2를 최대 시간으로 기준을 잡는다.
         */
        int time = 128000000;
        /**
         * while문 시작시 max에서 -1 되므로, 시작을 max에 +1 해주고 시작. 
         */
        floor++;
        
        while(floor-->=0) {
            int inventory = B;
            int removedBlock = 0;
            int needs = 0;
            for(int i=0; i<N*M ; i++) {
                int block = rand.get(i);
                if(block>floor) {
                    inventory += block - floor;
                    removedBlock += block - floor;
                }
                else needs += floor - block;
            }
            
            // 채워야 할 블록보다 가진 블록이 적을 경우 다음 층으로 내려감
            if(inventory<needs) continue;
            
            // 현재 층 작업시간 계산
            int tempTime = (removedBlock * 2) + needs;
            
            // 이전 시간이 현재 층보다 작업시간이 적은 경우, 한 층 빠진만큼 +1
            if(time <= tempTime) {
                floor++;
                break;
            } else {
                // 현재 층의 작업시간이 더 적을 경우, 현재 작업 시간을 기준시간에 세팅 후 아래층으로 이동 
                time = tempTime;
            }
        }

        System.out.println(""+time+" "+floor);
    }
}

---

레퍼런스 코드

참고 링크 : https://developer-hm.tistory.com/190