๋ฌธ์ (Gold 4)
https://www.acmicpc.net/problem/14658
14658๋ฒ: ํ๋์์ ๋ณ๋ฅ๋ณ์ด ๋น๋ฐ์น๋ค
์ฒซ์งธ ์ค์ ๋ค ์ ์ N, M, L, K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N์ ๋ณ๋ฅ๋ณ์ด ๋จ์ด์ง๋ ๊ตฌ์ญ์ ๊ฐ๋ก๊ธธ์ด, M์ ์ธ๋ก๊ธธ์ด, L์ ํธ๋จํ๋ฆฐ์ ํ ๋ณ์ ๊ธธ์ด, K๋ ๋ณ๋ฅ๋ณ์ ์๋ฅผ
www.acmicpc.net
ํ์ด
N๊ณผ M์ ๋ฒ์๊ฐ 500,000๊น์ง์ด๋ฏ๋ก, ์ด๋ฅผ ๋ชจ๋ ์์ ํ์ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.
ํ์ง๋ง, K์ ๊ฐ์๋ 100๊ฐ ์ดํ์ด๊ธฐ ๋๋ฌธ์ K๋ฅผ ์ด์ฉํด์ ํ์์ ์งํํ๋ฉด ๋๋ค.
์์ ์ฌ์ง์ ๋ฌธ์ ์์๋ฅผ ์ขํ์ ๋ํ๋ธ ๊ฒ์ด๋ค.
๋ณ๋ค์ ์ด์ค for๋ฌธ์ผ๋ก ๋๋ฉฐ, ๊ฐ๊ฐ์์ x์ขํ y์ขํ๋ฅผ ์ถ์ถํ์ฌ ๊ทธ ๋ฒ์๋ฅผ ํ์ํ๋ค.
๋นจ๊ฐ์ ์ ์ ๊ฐ ๋ฒํธ์์ ์ถ์ถ๋ x, y์ขํ๋ฅผ ๋ํ๋ด๊ณ ์ด๋ฅผ ์ข์๋จ์ผ๋ก ํ์ฌ L*L๋งํผ์ ๋ฒ์๋ฅผ ํ์ํ๋ฉด ๋๋ค.
๋ณ๋ค์ด ๋ชจ์๋ฆฌ์ ์กด์ฌํ๊ฒ ํ ์๋ก, ๋ ๋ง์ ๋ณ๋ค์ ํฌํจํ ์ ์๋ค๋ ๊ด์ ์ด๋ค.
์ ์์์ ๊ฒฝ์ฐ์์๋ 5๋ฒ ์ ์ x๋ฅผ ์ถ์ถํ๊ณ 2๋ฒ์ ์ y๋ฅผ ์ถ์ถํ ๋นจ๊ฐ ์ ์์ ํธ๋จํ๋ฆฐ์ ๋์์ ๋,
๊ฐ์ฅ ๋ง์ ๋ณ์ ํฌํจํ๊ฒ ๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค!
์ฝ๋
package bruteForce;
import java.util.*;
import java.io.*;
public class BOJ_14658_ํ๋์์๋ณ๋ฅ๋ณ์ด๋น๋ฐ์น๋ค {
static int N, M, L, K;
static List<int[]> stars;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
stars = new ArrayList<>();
for(int i =0 ; i < K ; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
stars.add(new int[]{x, y});
}
int res = Integer.MIN_VALUE;
for(int[] s1: stars){
for(int[] s2: stars){
res = Math.max(res, boundStar(s1[0], s2[1]));
}
}
System.out.println(K-res);
}
private static int boundStar(int i, int j) {
int res = 0;
for(int[] s:stars){
if(i<=s[0]&&s[0]<=i+L && j<=s[1]&&s[1]<=j+L ) res++;
}
return res;
}
}
์ ์ถ
500,000*500,000์ ์ํํ๋ ค ํด์ ์คํจ! ( ์๋๋๊ฑด ์์ง๋ง ํน์๋~ํด์ ํธ๋ผ์ด! )
'๐ ์๊ณ ๋ฆฌ์ฆ > BruteForce' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 6987๋ฒ ์๋์ปต(Java) (0) | 2022.02.08 |
---|---|
[SWEA] 3234๋ฒ ์คํ์ด์ ์ํ์ ์ธ(java) (0) | 2021.08.20 |
[SWEA] 4012๋ฒ ์๋ฆฌ์ฌ, [๋ฐฑ์ค] 14889๋ฒ ์คํํธ์ ๋งํฌ (0) | 2021.08.18 |
[๋ฐฑ์ค] 2961๋ฒ ๋์์ด๊ฐ ๋ง๋ ๋ง์๋ ์์ (0) | 2021.08.17 |
[๋ฐฑ์ค]17281๋ฒ โพ(์ผ๊ตฌ) (0) | 2021.08.17 |