๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] 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);
}
}