๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.1449 ์ˆ˜๋ฆฌ๊ณต ํ•ญ์Šน ๋ฌธ์ œ ํ’€์ด

๐Ÿ“– ๋ฌธ์ œ

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

ํ•ญ์Šน์ด๋Š” ํ’ˆ์งˆ์ด ์‹ฌ๊ฐํ•˜๊ฒŒ ๋‚˜์œ ์ˆ˜๋„ ํŒŒ์ดํ”„ ํšŒ์‚ฌ์˜ ์ˆ˜๋ฆฌ๊ณต์ด๋‹ค. ํ•ญ์Šน์ด๋Š” ์„ธ์ค€ ์ง€ํ•˜์ฒ  ๊ณต์‚ฌ์—์„œ ๋ฌผ์ด ์ƒŒ๋‹ค๋Š” ์†Œ์‹์„ ๋“ฃ๊ณ  ์ˆ˜๋ฆฌ๋ฅผ ํ•˜๋Ÿฌ ๊ฐ”๋‹ค.

ํŒŒ์ดํ”„์—์„œ ๋ฌผ์ด ์ƒˆ๋Š” ๊ณณ์€ ์‹ ๊ธฐํ•˜๊ฒŒ๋„ ๊ฐ€์žฅ ์™ผ์ชฝ์—์„œ ์ •์ˆ˜๋งŒํผ ๋–จ์–ด์ง„ ๊ฑฐ๋ฆฌ๋งŒ ๋ฌผ์ด ์ƒŒ๋‹ค.

ํ•ญ์Šน์ด๋Š” ๊ธธ์ด๊ฐ€ L์ธ ํ…Œ์ดํ”„๋ฅผ ๋ฌดํ•œ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

ํ•ญ์Šน์ด๋Š” ํ…Œ์ดํ”„๋ฅผ ์ด์šฉํ•ด์„œ ๋ฌผ์„ ๋ง‰์œผ๋ ค๊ณ  ํ•œ๋‹ค. ํ•ญ์Šน์ด๋Š” ํ•ญ์ƒ ๋ฌผ์„ ๋ง‰์„ ๋•Œ, ์ ์–ด๋„ ๊ทธ ์œ„์น˜์˜ ์ขŒ์šฐ 0.5๋งŒํผ ๊ฐ„๊ฒฉ์„ ์ค˜์•ผ ๋ฌผ์ด ๋‹ค์‹œ๋Š” ์•ˆ ์ƒŒ๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค.

๋ฌผ์ด ์ƒˆ๋Š” ๊ณณ์˜ ์œ„์น˜์™€, ํ•ญ์Šน์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํ…Œ์ดํ”„์˜ ๊ธธ์ด L์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ•ญ์Šน์ด๊ฐ€ ํ•„์š”ํ•œ ํ…Œ์ดํ”„์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

ํ…Œ์ดํ”„๋ฅผ ์ž๋ฅผ ์ˆ˜ ์—†๊ณ , ํ…Œ์ดํ”„๋ฅผ ๊ฒน์ณ์„œ ๋ถ™์ด๋Š” ๊ฒƒ๋„ ๊ฐ€๋Šฅํ•˜๋‹ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

Q.1449 ์ˆ˜๋ฆฌ๊ณต ํ•ญ์Šน ๋ฌธ์ œ ํ’€์ด์ž…๋‹ˆ๋‹ค.

์ฃผ์–ด์ง„ ํŒŒ์ดํ”„์— ๋ฌผ์ด ์ƒˆ๋Š” ์œ„์น˜๋“ค์„ ๋ฉ”๊พธ๋Š”๋ฐ ํ•„์š”ํ•œ ํ…Œ์ดํ”„์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋ฌผ์ด ์ƒˆ๋Š” ์œ„์น˜๊ฐ€ ๊ผญ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค๋Š” ๋ง์ด ์—†์œผ๋ฏ€๋กœ

๋ฌผ์ด ์ƒˆ๋Š” ์œ„์น˜๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ ์‹œ์ผœ์ค๋‹ˆ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ์•ž์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํ…Œ์ดํ”„๋ฅผ ๋ถ™์—ฌ์ฃผ๋ฉฐ

ํ…Œ์ดํ”„ ๊ธธ์ด์— ๋”ฐ๋ผ ๋‹ค์Œ ์ƒˆ๋Š” ์œ„์น˜๊นŒ์ง€ ์ปค๋ฒ„๊ฐ€ ๋˜๋Š”์ง€๋ฅผ ํ™•์ธํ•ด์ฃผ๊ณ 

์ปค๋ฒ„๊ฐ€ ๋˜์ง€ ์•Š๋Š” ์œ„์น˜๋งˆ๋‹ค ํ…Œ์ดํ”„๋ฅผ ๋ถ™์—ฌ์ฃผ๋ฉด

์ตœ์†Œํ•œ์˜ ๊ฐœ์ˆ˜์˜ ํ…Œ์ดํ”„๋กœ ๋ชจ๋“  ๋ฌผ์ด ์ƒˆ๋Š” ํŒŒ์ดํ”„๋ฅผ ์ปค๋ฒ„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ •๋ ฌํ•œ ํ›„ ์•ž์—์„œ๋ถ€ํ„ฐ ํ…Œ์ดํ”„๋ฅผ ๋ถ™์ด๋˜ ๊ธด ํ…Œ์ดํ”„๋ฅผ ๋ถ™์ด๋ฉด ๋‹ค๋ฅธ ์œ„์น˜๊นŒ์ง€๋„

์ปค๋ฒ„๊ฐ€ ๋  ์ˆ˜ ์žˆ์œผ๋‹ˆ

current ๋ผ๋Š” ๋ณ€์ˆ˜์— ํ˜„์žฌ ํ…Œ์ดํ”„๋ฅผ ๋ถ™์—ฌ ์ปค๋ฒ„๊ฐ€ ๋˜๋Š” ์œ„์น˜๋ฅผ ํ‘œ์‹œํ•ด์ค๋‹ˆ๋‹ค.

current๋กœ ์ปค๋ฒ„๊ฐ€ ๋˜์ง€ ์•Š๋Š” ๊ณณ์— ํ…Œ์ดํ”„๋ฅผ ์ƒˆ๋กœ ๋ถ™์—ฌ์ฃผ๊ณ  current๋ฅผ ๊ฐฑ์‹ ์‹œ์ผœ์ฃผ๋ฉด

๋‹ต์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ

package problem.greedy;

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

public class Main_1449 {

    static int N;
    static int L;
    static int[] position;
    static int count = 0;
    static int current = 0;

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        L = Integer.parseInt(input[1]);
        position = new int[N];
        String in[] = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            position[i] = Integer.parseInt(in[i]);
        }
        br.close();
    }

    public static void solve() {
        Arrays.sort(position);

        for (int i = 0; i < N; i++) {
            if (position[i] > current) {
                current = position[i] + L - 1;
                count++;
            }
        }
        System.out.println(count);

    }
}

Written on February 1, 2021