[백준] 18111번 : 마인크래프트 - JAVA

 

 

18111 마인크래프트

 

 

 

이번 문제는 1%에서 틀렸다고 나왔는데 아직 해당 문제의 원인을 찾지 못했다...

 

원인을 계속 찾아보는데 시간이 너무 오래 걸릴 것 같아 기존에 듣던 인강을 마저 듣기로 하고 내일 다시 문제를 풀 예정이다.

 

오늘까지 작성한 소스는 아래와 같다.

 

실패한 소스

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

	// 최대 인벤토리 크기
        final int MAX_INVEN_SIZE = 64000000;
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int[][] arrCraft = new int[n][m];
        
        int maxHeight = -1;
        int minTime = 64000001 * 2;

        // 가장 작은 값부터 큰 값까지 반복문을 돌려주기 위한 변수
        int max = -1;
        int min = 257;

        // 입력
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int input = Integer.parseInt(st.nextToken());
                arrCraft[i][j] = input;

                max = Math.max(input, max);
                min = Math.min(input, min);
            }
        }

        // 최소 높이부터 최대 높이까지 반복문을 돌려준다.
        for (int i = min; i <= max; i++) {
            // 실패 여부
            boolean isFail = false;
            // 땅을 평평하게 만드는데 걸린 총시간
            int time = 0;
            // 인벤토리의 블록 개수(임시 변수)
            int invenCnt = b;

            outer:
            for(int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    int tempHeight = arrCraft[j][k];

                    if (i == tempHeight) continue;

                    // 인벤토리에서 블록을 꺼내어 땅을 채워야 하는 경우 (1초)
                    if (i > tempHeight) {
                        int subtraction = i - tempHeight;

                        // 인벤토리 블록 개수가 부족한 경우 반복문 종료
                        if (invenCnt < subtraction) {
                            isFail = true;
                            break outer;
                        }

                        // 인벤토리 개수, 걸린 시간, 높이 세팅
                        tempHeight += subtraction;
                        time += subtraction;
                        invenCnt -= subtraction;
                    }

                    // 땅 블록을 회수해야 하는 경우 (2초)
                    if (i < tempHeight) {
                        int addition = tempHeight - i;

                        // 인벤토리 크기보다 회수한 블록의 개수가 많은 경우 반복문 종료
                        if (MAX_INVEN_SIZE < addition) {
                            isFail = true;
                            break outer;
                        }
					
                        // 인벤토리 개수, 걸린 시간, 높이 세팅 
                        tempHeight -= addition;
                        time += addition * 2;
                        invenCnt += addition;
                    }
                }
            }

            // 시간이 동일하게 걸리면 제일 높이가 높은 것을 출력
            if (!isFail && minTime == time) {
                maxHeight = Math.max(i, maxHeight);
            }

            // 시간이 제일 적게 걸리는 경우 시간과 높이를 세팅
            if (!isFail && minTime > time) {
                minTime = time;
                maxHeight = i;
            }
        }

        System.out.println(minTime + " " + maxHeight);
        br.close();
    }
}

 

 

오늘도 역시 쉽지 않은 알고리즘...

---

2024.04.27 토요일 추가

위 소스는 2차원 배열을 사용하였지만 다시 작업한 소스는 1차원 배열을 사용하였다.

 

실패한 이유는 다음과 같았다.

초기 인벤토리가 비어있는 상태에서 블록을 꺼내려고 하였고 블록을 꺼낼 때 반복문을 break로 탈출함

 

결과적으로 초기에 인벤토리가 비어있는 경우도 생각해야 하였으며 가장 높은 땅의 높이부터 블록을 회수하는 반복문을 먼저 작업하였다.

 

성공한 소스

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

        final int MAX_INVEN_SIZE = 64000000;
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int[] arrCraft = new int[n * m];

        // 가장 큰 값부터 작은 값까지 반복문을 돌려주기 위한 변수
        int max = -1;
        int min = 257;

        // 입력
        int idx = 0;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int input = Integer.parseInt(st.nextToken());
                arrCraft[idx++] = input;

                max = Math.max(input, max);
                min = Math.min(input, min);
            }
        }

        int maxHeight = -1;
        int minTime = 64000001 * 2;

        // 땅을 평평하게 만드는 시간이 동일하면 높이가 가장 큰 값을 출력하므로 max 높이부터 반복문 진행
        for (int i = max; i >= min; i--) {
            boolean isFail = false;
            int time = 0;
            int invenCnt = b;

            /*
            초기에 인벤토리가 비어있는 경우에도 가장 높은 땅의 높이부터 땅을 파서
            인벤토리에 블록을 넣을 수 있으니 블록을 회수하는 반복문을 먼저 작업한다.
             */
            for(int j = 0; j < n * m; j++) {
                // 땅 블록을 회수해야 하는 경우 (2초)
                if (i < arrCraft[j]) {
                    int addition = arrCraft[j] - i;

                    // 인벤토리 크기보다 회수한 블록의 개수가 많은 경우
                    if (MAX_INVEN_SIZE < invenCnt) {
                        isFail = true;
                        break;
                    }

                    time += addition * 2;
                    invenCnt += addition;
                }
            }

            // 인벤토리에서 블록을 꺼내어 땅을 채우는 경우 (1초)
            for(int j = 0; j < n * m; j++) {
                if (i > arrCraft[j]) {
                    int subtraction = i - arrCraft[j];

                    // 인벤토리 블록 개수가 부족한 경우
                    if (invenCnt < subtraction) {
                        isFail = true;
                        break;
                    }

                    time += subtraction;
                    invenCnt -= subtraction;
                }
            }

            // 시간이 제일 적게 걸리는 경우 시간과 높이를 세팅
            if (!isFail && minTime > time) {
                minTime = time;
                maxHeight = i;
            }
        }

        System.out.println(minTime + " " + maxHeight);
        br.close();
    }
}

 

 

드디어 백준과 연계된 solved 사이트에서 CLASS 2를 모두 풀었다.

 

CLASS 3부터는 DFS, BFS, DP 알고리즘이 본격적으로 나오니까 더 재밌어질 것 같다.

 

근데 알고리즘 푸는 시간이 오래 걸리니까 인강을 들을 시간이 적어지네...

 

https://solved.ac/

solved.ac

 

gold 5