[BOJ] 15459번 Haybale Feast

1. 이해하기

• 음식을 준비하는데 각 음식에는 맛과 매운 정도가 있다. 한 코스를 준비하는데 그 코스의 전체 맵기는 코스 내의 전체 요리 중 가장 높은 맵기로 결정이 된다. 코스는 연속된 음식을 말한다.

• 이때, 적어도 M의 맛이 되면서 준비할 수 있는 코스 중 맵기가 가장 낮은 코스를 알아내는 문제이다.

• 유니온 파인드를 응용해서 문제를 풀 수 있다. 각 노드의 부모를 담았던 배열에 맛을 저장한다.

• 맵기를 기준으로 정렬할 배열이 필요하다. 이때 이 배열이 담고 있어야할 정보는 맵기와 이 요리의 인덱스이다. 인덱스가 필요한 이유는 양 옆에 코스로 만들 수 있는 음식이 있고 그 음식과 같이 함께 코스로 나갈 수 있도록 union 할 때 필요한 정보이기 때문이다.

• 맵기를 기준으로 정렬한 후 낮은 맵기부터 차례로 살펴보며 양 옆에 합칠 수 있는 요리가 있는지 살핀다. 있다면 합치고 없다면 넘어간다.

• 이후에 현재의 코스의 맛이 M이 넘는지 확인하고 넘는다면 즉시 종료하고 그때의 맵기를 출력한다.

• 그때의 맵기를 출력하는 이유는 이때의 맵기가 코스 내의 맵기 중 가장 큰 값이기 때문이다.

---

2. 전체 코드

import java.util.Arrays;
import java.util.Scanner;

public class Boj15459_HaybaleFeast {
    static int N;
    static long M;
    static long[] p;
    static P[] fs;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextLong();
        p = new long[N];
        fs = new P[N];
        for(int i = 0; i < N; i++) {
            p[i] = -sc.nextLong();
            fs[i] = new P(i,sc.nextLong());
        }

        Arrays.sort(fs,(p1,p2) -> {
            return Long.compare(p1.s, p2.s);
        });

        boolean[] check = new boolean[N];
        for(int i = 0; i < N; i++) {
            int x = fs[i].i;
            long s = fs[i].s;
            check[x] = true;

            if(x > 0 && check[x-1]) union(x,x-1);
            if(x < N-1 && check[x+1]) union(x,x+1);
            if(-p[find(x)] >= M) {
                System.out.println(s);
                break;
            }
        }
        sc.close();
    }

    static int find(int x) {
        if(p[x] < 0) return x;
        return (int)(p[x] = find((int)p[x]));
    }

    static void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a==b) return;
        p[a]+=p[b];
        p[b]=a;
    }

    static class P {
        int i;
        long s;

        P(int i, long s) {
            this.i = i;
            this.s = s;
        }
    }
}

---

이 문제는 스스로 생각해내지 못해서 다른 사람의 코드를 참고했다.

https://github.com/kks227/BOJ/blob/master/15400/15459.cpp