[Boj_22254] ๊ณต์ • ์ปจ์„คํ„ดํŠธ ํ˜ธ์„

๐Ÿ“Ž ๋ฌธ์ œ ๋งํฌ

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

 

โ–ธ ๋ฌธ์ œ

๊ฑฐ๋“ญ๋œ ์ฐฝ์—… ์„ฑ๊ณต์„ ์ด๋ฃฌ ๋ฅ˜์ง„๊ตญ ์‚ฌ์žฅ์€ ์ด๋ฒˆ์—๋Š” ๋งž์ถคํ˜• ์„ ๋ฌผ์„ ์ œ์ž‘ํ•ด์ฃผ๋Š” ๊ณต์žฅ์„ ๋งŒ๋“ค๊ธฐ๋กœ ํ–ˆ๋‹ค. ํ˜„์žฌ ๋“ค์–ด์˜จ ๋งž์ถคํ˜• ์„ ๋ฌผ ์ฃผ๋ฌธ์€ ์ด N๊ฐœ์ด๋ฉฐ, ๊ฐ ๋งž์ถคํ˜• ์„ ๋ฌผ๋งˆ๋‹ค ์ œ์ž‘์— ํ•„์š”ํ•œ ์‹œ๊ฐ„์ด ์ •ํ•ด์ ธ์žˆ๋‹ค. ์ฃผ๋ฌธ์˜ ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋งค๊ฒจ์ ธ ์žˆ์œผ๋ฉฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์— ๋งž๊ฒŒ ๊ณต์ •์ด ์ด๋ค„์ง„๋‹ค.

  1. ๊ณต์ • ๋ผ์ธ์ด ์ด K๊ฐœ๊ฐ€ ์žˆ๋‹ค๋ฉด 1๋ฒˆ๋ถ€ํ„ฐ K๋ฒˆ๊นŒ์ง€์˜ ๋ฒˆํ˜ธ๊ฐ€ ์กด์žฌํ•œ๋‹ค.
  2. ๊ณต์ • ๋ผ์ธ์˜ ์‚ฌ์šฉ ์‹œ๊ฐ„์€ ๋ฐฐ์ •๋œ ๋งž์ถคํ˜• ์„ ๋ฌผ๋“ค์˜ ์ œ์ž‘ ์‹œ๊ฐ„์˜ ์ดํ•ฉ์ด๋‹ค.
  3. โ€Ši๋ฒˆ ์„ ๋ฌผ์€ 1๋ฒˆ ๋ถ€ํ„ฐ i−1๋ฒˆ ์„ ๋ฌผ๋“ค์ด ๋ฐฐ์ •๋œ ์ดํ›„์— ์‚ฌ์šฉ ์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์ ์€ ๊ณต์ • ๋ผ์ธ ์ค‘ ํ•˜๋‚˜์— ๋ฐฐ์ •๋œ๋‹ค.

๋ชจ๋“  ๋งž์ถคํ˜• ์„ ๋ฌผ์˜ ์ œ์ž‘์ด ์™„๋ฃŒ๋  ๋•Œ๊นŒ์ง€ ์ตœ๋Œ€ X์‹œ๊ฐ„์ด ๋‚จ์•„์žˆ๋Š” ์ƒํ™ฉ์ธ๋ฐ, ์•„์ง ๊ณต์ • ๋ผ์ธ์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ •ํ•ด์ ธ ์žˆ์ง€ ์•Š๋‹ค. ๋ฅ˜์ง„๊ตญ ์‚ฌ์žฅ์€ ์ด ๋ถ„์•ผ ์ตœ๊ณ  ๊ถŒ์œ„์ž, ๊ณต์ • ์ปจ์„คํ„ดํŠธ ํ˜ธ์„์—๊ฒŒ ์˜๋ขฐํ–ˆ๋‹ค. ๊ณต์ • ์ปจ์„คํ„ดํŠธ ํ˜ธ์„์€ ์ตœ์†Œํ•œ์˜ ๋น„์šฉ์„ ์“ฐ๊ธฐ ์œ„ํ•ด์„œ ๊ณต์ • ๋ผ์ธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ตœ์†Œํ™” ์‹œํ‚ค๊ณ ์ž ํ•œ๋‹ค. ํ˜ธ์„์„ ๋„์™€ ํ•„์š”ํ•œ ์ตœ์†Œ ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜์ž.

 

โ–ธ ์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์— ๋งž์ถคํ˜• ์„ ๋ฌผ ์ฃผ๋ฌธ์˜ ๊ฐœ์ˆ˜ N, ์ œ์ž‘ ์™„๋ฃŒ๊นŒ์ง€ ๋‚จ์€ ์‹œ๊ฐ„ X๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค.

๋‘ ๋ฒˆ์งธ ์ค„์—๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ ์„ ๋ฌผ์ด ํ•„์š”ํ•œ ๊ณต์ • ์‹œ๊ฐ„์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ์œ„๋Š” '์‹œ๊ฐ„' ์ด๋‹ค.

 

โ–ธ ์ถœ๋ ฅ

๋ชจ๋“  ์„ ๋ฌผ์„ X์‹œ๊ฐ„ ์ด๋‚ด์— ์ œ์ž‘ํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋ผ.

 

โ–ธ ์ œํ•œ

  • 1≤N≤100,000, N์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.
  • โ€Š1≤X≤10 ^9, X๋Š” ์ž์—ฐ์ˆ˜์ด๋‹ค.
  • โ€Š1≤ ๊ฐ ์„ ๋ฌผ์˜ ๊ณต์ • ์‹œ๊ฐ„ ≤X, ๋ชจ๋“  ์‹œ๊ฐ„์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

 

๐Ÿ“ ๋ฌธ์ œ ์ •๋ณด

  • ๐Ÿฅ‡  ๋ฌธ์ œ ๋ ˆ๋ฒจ : ๊ณจ๋“œ 3
  • ๐Ÿ””  ๋ฌธ์ œ ์œ ํ˜• : ์ž๋ฃŒ ๊ตฌ์กฐ, ์ด๋ถ„ ํƒ์ƒ‰, ์šฐ์„ ์ˆœ์œ„ ํ, ๋งค๊ฐœ ๋ณ€์ˆ˜ ํƒ์ƒ‰
  • ๐Ÿ’ฌ  ํ’€์ด ์–ธ์–ด : JAVA

 

๐Ÿค” ๋ฌธ์ œ ํ’€์ด

๊ฐ ์„ ๋ฌผ๋งˆ๋‹ค ์ œ์ž‘์— ํ•„์š”ํ•œ ์‹œ๊ฐ„์ด ์ •ํ•ด์ ธ ์žˆ์„ ๋•Œ,

์ตœ๋Œ€ x์‹œ๊ฐ„ ์ด๋‚ด์— ๋ชจ๋“  ์„ ๋ฌผ์„ ์ œ์ž‘ํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ๊ณต์ • ๋ผ์ธ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

 

์ด ๋ฌธ์ œ๋Š” ์ด๋ถ„ ํƒ์ƒ‰๊ณผ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

 

๐Ÿ”น ๊ณต์ • ๋ผ์ธ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ด๋ถ„ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค.

๊ณต์ • ๋ผ์ธ์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋Š” 1๊ฐœ, ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋Š” ์„ ๋ฌผ์˜ ๊ฐœ์ˆ˜์ธ n๊ฐœ๋‹ค.

mid๊ฐœ์˜ ๊ณต์ • ๋ผ์ธ์œผ๋กœ x์‹œ๊ฐ„ ์ด๋‚ด์— ์ œ์ž‘์ด ๊ฐ€๋Šฅํ•˜๋ฉด, ๋” ์ž‘์€ ๊ฐœ์ˆ˜๋กœ๋„ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.

๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด, ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜๋ฅผ ๋Š˜๋ ค์•ผ ํ•˜๋ฏ€๋กœ ๋” ํฐ ๋ฒ”์œ„๋ฅผ ํƒ์ƒ‰ํ•œ๋‹ค.

 

๐Ÿ”น mid๊ฐœ์˜ ๊ณต์ • ๋ผ์ธ์—์„œ ์„ ๋ฌผ์„ ๋ฐฐ์ •ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

ํ˜„์žฌ๊นŒ์ง€ ์‚ฌ์šฉ๋œ ๊ณต์ • ์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์ ์€ ๋ผ์ธ์— ์ƒˆ๋กœ์šด ์„ ๋ฌผ์„ ๋ฐฐ์ •ํ•œ๋‹ค.

์„ ๋ฌผ์„ ๋ฐฐ์ •ํ•˜๋ฉด์„œ ์ด ์‹œ๊ฐ„์ด x๋ฅผ ์ดˆ๊ณผํ•˜๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•ด mid๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ ํƒ์ƒ‰ํ•˜๋„๋ก ํ•œ๋‹ค.

 

์œ„ ํ’€์ด๋ฅผ ์ฝ”๋“œ๋กœ ์ž‘์„ฑํ•ด ๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

 

โœ” ์ตœ์ข… ์ฝ”๋“œ

๋ฉ”๋ชจ๋ฆฌ : 77216KB
์‹œ๊ฐ„ : 868ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, x;
    static int[] ProcessTime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // ์„ ๋ฌผ ์ฃผ๋ฌธ ๊ฐœ์ˆ˜
        x = Integer.parseInt(st.nextToken()); // ์ œ์ž‘ ์™„๋ฃŒ๊นŒ์ง€ ๋‚จ์€ ์‹œ๊ฐ„

        ProcessTime = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            ProcessTime[i] = Integer.parseInt(st.nextToken());
        }

        int start = 1;
        int end = n;
        while (start <= end) {
            int mid = start + (end-start) / 2; // ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜

            if (isPossible(mid)) { // ํ˜„์žฌ ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜๋กœ ์‹œ๊ฐ„์— ๋งž์ถฐ ์ œ์ž‘์„ ๋๋‚ผ ์ˆ˜ ์žˆ๋‹ค๋ฉด
                end = mid-1;
            } else start = mid+1;
        }

        System.out.println(start);
    }

    private static boolean isPossible(int mid) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < mid; i++) { // ๊ณต์ • ๋ผ์ธ ๊ฐœ์ˆ˜๋งŒํผ 0(์‹œ๊ฐ„)์œผ๋กœ ์ฑ„์šฐ๊ธฐ
            pq.offer(0);
        }
        for (int i = 0; i < n; i++) {
            int nowTime = pq.poll();

            // ์‹œ๊ฐ„ ์•ˆ์— ๋๋‚ด์ง€ ๋ชปํ•จ
            if (nowTime+ProcessTime[i] > x) return false;
            pq.offer(nowTime+ProcessTime[i]);
        }
        return true;
    }
}

 

๊ณจ๋“œ 3 ๋ฌธ์ œ์ธ๋ฐ ์ƒ๊ฐ๋ณด๋‹ค ์–ด๋ ต์ง€ ์•Š๊ฒŒ ํ’€์—ˆ๋‹ค. ์ด๋ถ„ ํƒ์ƒ‰ ๋ฌธ์ œ์— ๊ฐ์ด ์žกํ˜€๊ฐ€๋Š” ๊ฒƒ ๊ฐ™์•„์„œ ๋ฟŒ๋“ฏํ•˜๋‹ค. ๐Ÿ˜

์šฐ์„ ์ˆœ์œ„ ํ๋กœ ํ•ด๊ฒฐํ•˜๋Š” ๋ถ€๋ถ„์€ ์ด ๋ฌธ์ œ์™€ ์œ ์‚ฌํ–ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

ํ•ด๊ฒฐ ์™„๋ฃŒ ! ๐Ÿ”ฅ

 

'Algorithm > BOJ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Boj_2696] ์ค‘์•™๊ฐ’ ๊ตฌํ•˜๊ธฐ  (0) 2025.02.15
[Boj_12014] ์ฃผ์‹, LIS  (0) 2025.02.11
[Boj_5214] ํ™˜์Šน  (0) 2025.01.31
[Boj_16509] ์žฅ๊ตฐ  (0) 2025.01.30
[Boj_1854] K๋ฒˆ์งธ ์ตœ๋‹จ๊ฒฝ๋กœ ์ฐพ๊ธฐ  (0) 2025.01.25