[ STUDY ]/CodingTest

백준 18111 : 마인 크래프트

김강니 2024. 12. 3. 21:30

 

일정한 높이의 땅을 만드는데 최소 시간과 땅높이 구하는 문제다...
일단 풀긴 풀었는데 코드가 너무 더러워서 코드 정리를 해보겟슴..

 

기존 코드ㅋㅋ

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

public class P18111 {
    static int N, M;
    static long B;
    static int[][] block;
    static int time, height;
    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()); //가로
        B = Long.parseLong(st.nextToken()); //가지고 있는 블록
        time = Integer.MAX_VALUE;
        height = 0;
        int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
        block = new int[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                block[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(max, block[i][j]);
                min = Math.min(min, block[i][j]);
            }
        }
        int diff = max - min;

        for(int i = 0; i <= diff; i++) { //높이 차이만큼 반복
            int t = 0; //총 시간 계산
            long b = B; // 블럭 수
            for(int j = 0; j < N; j++) {
                for(int a : block[j]) {
                    if(a > min) {
                        t += (a - min) * 2; //땅 제거 : 2초
                        b += (a-min); //제거한 땅만큼
                    }else if(a < min){
                        b-= min - a; //땅 쌓기 : 1초
                        t += (min - a); //쌓은 땅만큼 인벤토리에서 빼기
                    }
                }
            }
            //공통 : 인벤토리에 블럭이 0 이상이고
            if(t < time && b >= 0){ //시간이 최소이면 갱신
                time = t;
                height = min;
            }else if(t == time && b >= 0){ //시간이 같으면 땅 높이 값 더 작은 것으로 갱신
                height = Math.max(height, min);
            }
            min++; //땅높이 한 칸 올림
        }

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

 

 

⚒️ 수정 후 코드

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

public class P18111 {
    static int N, M;
    static long B;
    static int[][] block;
    static int minHeight = Integer.MAX_VALUE;
    static int maxHeight = Integer.MIN_VALUE;
    static int optimalTime = Integer.MAX_VALUE;
    static int optimalHeight = 0;
    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()); //가로
        B = Long.parseLong(st.nextToken()); //가지고 있는 블록
        block = new int[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                block[i][j] = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, block[i][j]);
                minHeight = Math.min(minHeight, block[i][j]);
            }
        }

        for(int target = minHeight; target <= maxHeight; target++) {
            calculateTime(target);
        }

        System.out.println(optimalTime + " " + optimalHeight);
    }

    private static void calculateTime(int target) {
        int time = 0; //총 시간 계산
        long blocks = B; // 블럭 수
        
        for(int i = 0; i < N; i++) {
            for(int a : block[i]) {
                int diff = a - target;
                if(a > target) {
                    time += diff * 2; //땅 제거 : 2초
                    blocks += diff; //제거한 땅만큼
                }else if(a < target){
                    blocks += diff; //땅 쌓기 : 1초
                    time += -diff; //쌓은 땅만큼 인벤토리에서 빼기
                }
            }
        }
        
        if(blocks >= 0){//공통 : 인벤토리에 블럭이 0 이상이고
            if(time < optimalTime){ //시간이 최소이면 갱신
                optimalTime = time;
                optimalHeight = target;
            }else if(time == optimalTime){ //시간이 같으면 땅 높이 값 더 작은 것으로 갱신
                optimalHeight = Math.max(optimalHeight, target);
            }
        }
    }
}

 

  1. 시간 계산하는 함수를 따로 빼기
  2. 차이만큼 반복해서 min++ 하지 않고 애초에 범위를 min ~ max로 설정
  3. 땅을 제거하거나 쌓는 수를 계속 계산하지 않고 변수에 저장해서 재사용

'[ STUDY ] > CodingTest' 카테고리의 다른 글

백준 30804 : 과일 탕후루  (0) 2024.12.11
BFS, DFS 어려워여  (1) 2024.12.07
백준 1927 : 최소 힙  (3) 2024.11.26
백준 1260 : DFS와 BFS(오늘의 교훈 : 문제를 잘 읽자)  (2) 2024.11.25
11727 : 2 x n 타일링2 (DP)  (0) 2024.11.24