๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7568
- ์ด๋ค ์ฌ๋์ ๋ชธ๋ฌด๊ฒ๊ฐ x kg์ด๊ณ ํค๊ฐ y cm๋ผ๋ฉด ์ด ์ฌ๋์ ๋ฉ์น๋ (x, y)๋ก ํ์๋๋ค.
- ๋ ์ฌ๋ A ์ B์ ๋ฉ์น๊ฐ ๊ฐ๊ฐ (x, y), (p, q)๋ผ๊ณ ํ ๋ x > p ๊ทธ๋ฆฌ๊ณ y > q ์ด๋ผ๋ฉด ์ฐ๋ฆฌ๋ A์ ๋ฉ์น๊ฐ B์ ๋ฉ์น๋ณด๋ค "๋ ํฌ๋ค"๊ณ ๋งํ๋ค.
- ์๋ฅผ ๋ค์ด ์ด๋ค A, B ๋ ์ฌ๋์ ๋ฉ์น๊ฐ ๊ฐ๊ฐ (56, 177), (45, 165) ๋ผ๊ณ ํ๋ค๋ฉด A์ ๋ฉ์น๊ฐ B๋ณด๋ค ํฐ ์ ์ด ๋๋ค.
- ๊ทธ๋ฐ๋ฐ ์๋ก ๋ค๋ฅธ ๋ฉ์น๋ผ๋ฆฌ ํฌ๊ธฐ๋ฅผ ์ ํ ์ ์๋ ๊ฒฝ์ฐ๋ ์๋ค.
- ์๋ฅผ ๋ค์ด ๋ ์ฌ๋ C์ D์ ๋ฉ์น๊ฐ ๊ฐ๊ฐ (45, 181), (55, 173)์ด๋ผ๋ฉด ๋ชธ๋ฌด๊ฒ๋ D๊ฐ C๋ณด๋ค ๋ ๋ฌด๊ฒ๊ณ , ํค๋ C๊ฐ ๋ ํฌ๋ฏ๋ก, "๋ฉ์น"๋ก๋ง ๋ณผ ๋ C์ D๋ ๋๊ตฌ๋ ์๋๋ฐฉ๋ณด๋ค ๋ ํฌ๋ค๊ณ ๋งํ ์ ์๋ค.
- ์ฒซ ์ค์๋ ์ ์ฒด ์ฌ๋์ ์ N์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ด์ด์ง๋ N๊ฐ์ ์ค์๋ ๊ฐ ์ฌ๋์ ๋ชธ๋ฌด๊ฒ์ ํค๋ฅผ ๋ํ๋ด๋ ์์ ์ ์ x์ y๊ฐ ํ๋์ ๊ณต๋ฐฑ์ ๋๊ณ ๊ฐ๊ฐ ๋ํ๋๋ค.
- ์ฌ๋ฌ๋ถ์ ์ ๋ ฅ์ ๋์ด๋ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ฅผ ๊ตฌํด์ ๊ทธ ์์๋๋ก ์ฒซ ์ค์ ์ถ๋ ฅํด์ผ ํ๋ค. ๋จ, ๊ฐ ๋ฉ์น ๋ฑ์๋ ๊ณต๋ฐฑ๋ฌธ์๋ก ๋ถ๋ฆฌ๋์ด์ผ ํ๋ค.
์์ด๋์ด
- 2์ฐจ์ ๋ฐฐ์ด์ ๋ชธ๋ฌด๊ฒ์ ํค๋ฅผ ์ ์ฅํ๊ณ ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ๋ฉฐ ๋๊ฐ ๋ชจ๋ ํฐ ๊ฒฝ์ฐ๊ฐ ๋์ค๋ฉด ์นด์ดํธ + 1ํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์ ๋ฌธ์ ๋ฅผ ๋๋ฌด ๋ณต์กํ๊ฒ ์ดํดํด์ ์์ ์์ฒญ ๋ณต์กํ๊ฒ ์ ์๋ค๊ฐ ํ๋ฆฌ๊ณ ๋์ ์ ํ๋ ธ๋์ง ํ์ธํ๋ค...
- ์๊ณ ๋ณด๋ ๊ทธ๋ฅ ์๊ธฐ๋ณด๋ค ๋์ ์ฌ๋์ด ๋ช๋ช ์๋์ง๋ง ์ฐพ์ผ๋ฉด ๋๋ ๋ฌธ์ ์ฌ์ ๋๋ฌด ํํํ๋ค...ใ ใ
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ7568 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// ์ฌ๋๋ค์ ํค์ ๋ฌด๊ฒ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int people[][] = new int[N][2];
int rank[] = new int[N];
// ์ฌ๋์๋งํผ ๋ฐ๋ณต
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
// ๋ฐฐ์ด์ ๊ฐ ์ ์ฅ
people[i][0] = w;
people[i][1] = h;
}
for(int i = 0; i < N; i++){
// ์๊ธฐ๋ณด๋ค ๋์๊ฒ ๋ช๊ฐ ์๋์ง ์ธ๋ ๋ณ์
int cnt = 1;
for(int j = 0; j < N; j++){
// ๊ธฐ์ค ๋ชธ๋ฌด๊ฒ์ ํค๋ฅผ ๋น๊ตํ์ ๋, ๋ชจ๋ ํฐ ์ฌ๋์ด ์๋ค๋ฉด
if((people[i][0] < people[j][0]) && people[i][1] < people[j][1]){
// ์นด์ดํธ + 1
cnt = cnt + 1;
}
}
// ๋ญํฌ ๋ฐฐ์ด์ ์๋ก ๋ช๋ช
์๋์ง ๊ธฐ๋ก
rank[i] = cnt;
}
for(int i = 0; i < N; i++){
System.out.print(rank[i] + " ");
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 11650 ์ขํ ์ ๋ ฌํ๊ธฐ (0) | 2024.07.16 |
---|---|
[Java] BOJ 10814 ๋์ด์ ์ ๋ ฌ (2) | 2024.07.16 |
[Java] BOJ 2751 ์ ์ ๋ ฌํ๊ธฐ 2 (0) | 2024.07.15 |
[Java] BOJ 1676 ํฉํ ๋ฆฌ์ผ 0์ ๊ฐ์ (2) | 2024.07.14 |
[Java] BOJ 1436 ์ํ๊ฐ๋ ์ (4) | 2024.07.14 |