[Algo] 백준 1756 피자 굽기 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1756

메모리 : 64568KB

시간 : 568ms

언어 : Java 11

코드

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

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());
        int D = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[D + 1];
        int[] ans = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        arr[0] = Integer.MAX_VALUE;
        for (int i = 1; i <= D; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            // 앞 오븐의 크기만큼밖에 안들어감
            if (arr[i - 1] < arr[i]) {
                arr[i] = arr[i - 1];
            }
        }
        st = new StringTokenizer(br.readLine());
        // 맨 처음 피자 놓기
        int num = Integer.parseInt(st.nextToken());
        int depth = D;
        ans[1] = D;
        for (int i = 1; i <= D; i++) {
            // 피자가 걸리면 전칸에 놓기
            if (arr[i] < num) {
                ans[1] = i - 1;
                depth = i - 1;
                break;
            }
        }
        for (int i = 1; i < N; i++) {
            num = Integer.parseInt(st.nextToken());
            while (true) {
                depth--;
                if (depth <= 0) {
                    break;
                }
                // 피자가 들어가면
                if (arr[depth] >= num) {
                    ans[i + 1] = depth;
                    break;
                }
            }
        }
        System.out.println(ans[N]);
    }
}

풀이

맨 처음에 피자가 한 오븐에 두개씩도 들어가는줄 알았다.. 2짜리 피자 두 개가 4짜리 오븐에 들어간다고 생각해서 한참 틀렸다..ㅎㅎ 그냥 문맥상 안되는거였음.... 이해하기 참 어려운 문제였다

1. 오븐은 윗칸의 크기가 아랫칸을 모두 통제한다. 아래칸이 아무리 넓어도 윗칸의 크기만큼만 피자가 들어간다. 따라서 아래칸을 윗칸의 크기만큼 제한해 정렬을 한 효과를 준다.
2. 가장 처음 받는 피자의 자리를 잡는다. 그 밑의 depth로는 피자가 들어갈 수 없기 때문에 탐색해야할 depth는 첫번째 피자의 위쪽으로 제한된다.
3. 피자를 하나씩 받아보며 depth를 줄여나간다. 피자가 들어갈 수 있으면 피자를 넣고, 들어가지 않으면 윗칸으로 이동한다.