[백준] 1756번. 피자 굽기(JAVA)

문제

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

---

풀이

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

public class Main {

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

        // 오븐 깊이 D, 도우 개수 N 입력
        st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[] oven = new int[d];

        // 오븐 크기 입력
        st = new StringTokenizer(br.readLine());
        oven[0] = Integer.parseInt(st.nextToken());
        
        // 단조 감소 유지
        for (int i = 1; i < d; i++) {
            oven[i] = Math.min(oven[i - 1], Integer.parseInt(st.nextToken()));
        }

        int[] bread = new int[n];

        // 도우 크기 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            bread[i] = Integer.parseInt(st.nextToken());
        }

        int depth = d; // 오븐의 깊이 (1-based index로 생각)
        int idx = 0;   // 현재 도우의 인덱스

        // 오븐을 역순 탐색하면서 도우 배치
        for (int i = d - 1; i >= 0 && idx < n; i--) {
            if (bread[idx] <= oven[i]) { // 도우가 현재 위치에 들어갈 수 있다면
                depth = i + 1;  // 1-based index 유지
                idx++; // 다음 도우로 이동
            }
        }

        // 모든 도우가 배치되었다면 depth 출력, 그렇지 않다면 0 출력
        System.out.println(idx == n ? depth : 0);
    }
}

---

풀이 해설

이 문제를 풀며 느낀 것은 때로는 단순한 접근법이 더욱 확실하다는 것이다.

처음으로 문제를 접했을 때, 어떤 자료구조를 써야 할까? 어떤 알고리즘이 있을까?라는 방식으로 접근했다.

결과적으로 알고리즘이 떠오르지 않아 자료구조로 접근하게 되었고, 우선순위큐가 좋겠다! 라고 생각했다.

 

하지만, 실제 문제를 풀었으나 완벽하게 해결이 되지 않았고 원점으로 돌아가 다시 고민해 보았다.

 

문제의 주요한 포인트는 깊이에 따라 오븐의 사이즈가 모두 다를 수 있지만 한번 막히면 더 이상 내려갈 수 없다는 것이다.

 

예를 들어 깊이 1부터 5 4 3 2 1이라고 주어졌다면 실제로 5 4 3 2 1의 사이즈로 볼 수 있다.

만약 1 2 3 4 5라고 주어졌다면? 사실상 1 1 1 1 1이라고 봐도 무방하다는 것이다. 결과적으로 깊이에 따라 최솟값을 기록하며 사이즈로 저장하면 된다는 것이다.

 

이때도 문제가 발생했다. 기존에 작성해 둔 코드가 아까워 자료구조를 다시 고민하지 않고 우선순위큐로 해결하려고 했다. 하지만 실제로 시간복잡도상 배열이 좋다고 생각했고, 정답을 맞힐 수 있었다.