ํญ์น์ด๋ ํ์ง์ด ์ฌ๊ฐํ๊ฒ ๋์ ์๋ ํ์ดํ ํ์ฌ์ ์๋ฆฌ๊ณต์ด๋ค. ํญ์น์ด๋ ์ธ์ค ์งํ์ฒ ๊ณต์ฌ์์ ๋ฌผ์ด ์๋ค๋ ์์์ ๋ฃ๊ณ ์๋ฆฌ๋ฅผ ํ๋ฌ ๊ฐ๋ค.
ํ์ดํ์์ ๋ฌผ์ด ์๋ ๊ณณ์ ์ ๊ธฐํ๊ฒ๋ ๊ฐ์ฅ ์ผ์ชฝ์์ ์ ์๋งํผ ๋จ์ด์ง ๊ฑฐ๋ฆฌ๋ง ๋ฌผ์ด ์๋ค.
ํญ์น์ด๋ ๊ธธ์ด๊ฐ L์ธ ํ ์ดํ๋ฅผ ๋ฌดํ๊ฐ ๊ฐ์ง๊ณ ์๋ค.
ํญ์น์ด๋ ํ ์ดํ๋ฅผ ์ด์ฉํด์ ๋ฌผ์ ๋ง์ผ๋ ค๊ณ ํ๋ค. ํญ์น์ด๋ ํญ์ ๋ฌผ์ ๋ง์ ๋, ์ ์ด๋ ๊ทธ ์์น์ ์ข์ฐ 0.5๋งํผ ๊ฐ๊ฒฉ์ ์ค์ผ ๋ฌผ์ด ๋ค์๋ ์ ์๋ค๊ณ ์๊ฐํ๋ค.
๋ฌผ์ด ์๋ ๊ณณ์ ์์น์, ํญ์น์ด๊ฐ ๊ฐ์ง๊ณ ์๋ ํ ์ดํ์ ๊ธธ์ด L์ด ์ฃผ์ด์ก์ ๋, ํญ์น์ด๊ฐ ํ์ํ ํ ์ดํ์ ์ต์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ ์ดํ๋ฅผ ์๋ฅผ ์ ์๊ณ , ํ ์ดํ๋ฅผ ๊ฒน์ณ์ ๋ถ์ด๋ ๊ฒ๋ ๊ฐ๋ฅํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌผ์ด ์๋ ๊ณณ์ ๊ฐ์ N๊ณผ ํ ์ดํ์ ๊ธธ์ด L์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ๋ฌผ์ด ์๋ ๊ณณ์ ์์น๊ฐ ์ฃผ์ด์ง๋ค. N๊ณผ L์ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๊ณ , ๋ฌผ์ด ์๋ ๊ณณ์ ์์น๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํญ์น์ด๊ฐ ํ์ํ ํ ์ดํ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
1) ํํ
์ดํ๋ก ๋ถ์ผ ์ ์๋ ๋ฒ์ ๊ตฌํ๊ธฐ
2) ๊ทธ ๋ฒ์๋ฅผ ๋์ด๊ฐ๋ฉด ์๋ก์ด ํ
์ดํ ํ์ํ๊ณ , ๋์ด๊ฐ ๊ทธ ๋ถ๋ถ๋ถํฐ ์๋ก์ด ํ
์ดํ๋ฅผ ๋ถ์ฌ์ผํจ
1) ํํ ์ดํ๋ก ๋ถ์ผ ์ ์๋ ๋ฒ์ ๊ตฌํ๊ธฐ
arr[idx] ~ arr[idx] + L - 1
2) ๊ทธ ๋ฒ์๋ฅผ ๋์ด๊ฐ๋ฉด ์๋ก์ด ํ ์ดํ ํ์ํ๊ณ , ๋์ด๊ฐ ๊ทธ ๋ถ๋ถ๋ถํฐ ์๋ก์ด ํ ์ดํ๋ฅผ ๋ถ์ฌ์ผํจ
for (int j = idx + 1; j < N; j++) {
if (arr[idx] + L - 1 < arr[j]) {
count++;
idx = j;
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Greedy_8 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int L = Integer.parseInt(s[1]);
int arr[] = new int[N];
s = br.readLine().split(" ");
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(s[i]);
Arrays.sort(arr);
int count = 1;
int idx = 0;
for (int j = idx + 1; j < N; j++) {
if (arr[idx] + L - 1 < arr[j]) {
count++;
idx = j;
}
}
System.out.println(count);
}
}
์ฑ๊ณต~
(๋ ๋ฒ ์๋์ ์ฑ๊ณตํ๋๋ฐ.. ์ฒซ๋ฒ์งธ๊ฐ ์คํจํ๋ ์ด์ ๋ arrays.sort ์ํด์ค์..ใ
)