[백준] 1756: 피자 굽기 - JAVA

18 Jun 2023 in Algorithm on 구현

https://www.acmicpc.net/problem/1756

풀이

구현 + 그리디 문제.

피자 반죽을 오븐의 사이즈에 맞춰서 넣는데

위에서부터 내려가다가 오븐의 사이즈가 피자 사이즈보다 작으면 그 위칸에 위치한다.

예제에서 오븐의 사이즈가 { 5, 6, 4, 3, 6, 2, 3 } 으로 주어졌는데

두번째 칸에는 위에서부터 내려와야 하므로 최대 5 사이즈의 피자가 들어갈 수 있다.

따라서 오븐의 사이즈 배열을 { 5, 5, 4, 3, 3, 2, 2 } 와 같이 바꿔주었다.

단순하게 아래에서부터 탐색하여 위치를 찾는 방법과

이분탐색으로 위치를 찾는 방법이 있었다.

---

단순 탐색

메모리: 64440KB

시간: 532ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static int D, N, pos;
    static int[] oven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        D = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        oven = new int[D + 1];
        st = new StringTokenizer(br.readLine());
        oven[0] = Integer.MAX_VALUE;
        for (int i = 1; i < D + 1; i++) {
            oven[i] = Integer.parseInt(st.nextToken());
            oven[i] = Math.min(oven[i - 1], oven[i]);
        }

        st = new StringTokenizer(br.readLine());
        pos = D;
        for (int i = 0; i < N; i++) {
            int size = Integer.parseInt(st.nextToken());
            dropPizza(size);
        }

        System.out.println(pos);
    }

    private static void dropPizza(int size) {
        boolean flag = false;

        for (int i = pos; i > 0; i--) {
            if (size <= oven[i]) {
                pos = i;
                oven[i] = 0;
                flag = true;
                break;
            }
        }

        if (!flag) {
            pos = 0;
        }
    }

}

---

이분 탐색

메모리: 64200KB

시간: 528ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static int D, N, pos;
    static int[] oven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        D = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        oven = new int[D + 1];
        st = new StringTokenizer(br.readLine());
        oven[0] = Integer.MAX_VALUE;
        for (int i = 1; i < D + 1; i++) {
            oven[i] = Integer.parseInt(st.nextToken());
            oven[i] = Math.min(oven[i - 1], oven[i]);
        }

        st = new StringTokenizer(br.readLine());
        pos = D + 1;
        for (int i = 0; i < N; i++) {
            int size = Integer.parseInt(st.nextToken());
            binaryPizza(size, 0, pos - 1);
        }

        System.out.println(pos);
    }

    private static void binaryPizza(int size, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (size <= oven[mid]) {
                start = mid + 1;
                pos = mid;
            } else {
                end = mid - 1;
            }
        }
    }

}