-
[๋ฐฑ์ค(BOJ)] 7568๋ฒ ๋ฉ์น, C์ธ์ด ํ์ดPS(Problem Solving)/C 2020. 8. 3. 11:47๋ฐ์ํ
<๋ฉ์น>, 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๋ช ์ ์ง๋จ์์ ๊ฐ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ ์์ ๋ณด๋ค ๋ "ํฐ ๋ฉ์น"์ ์ฌ๋์ ์๋ก ์ ํด์ง๋ค. ๋ง์ผ ์์ ๋ณด๋ค ๋ ํฐ ๋ฉ์น์ ์ฌ๋์ด k๋ช ์ด๋ผ๋ฉด ๊ทธ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ k+1์ด ๋๋ค. ์ด๋ ๊ฒ ๋ฑ์๋ฅผ ๊ฒฐ์ ํ๋ฉด ๊ฐ์ ๋ฉ์น ๋ฑ์๋ฅผ ๊ฐ์ง ์ฌ๋์ ์ฌ๋ฌ ๋ช ๋ ๊ฐ๋ฅํ๋ค. ์๋๋ 5๋ช ์ผ๋ก ์ด๋ฃจ์ด์ง ์ง๋จ์์ ๊ฐ ์ฌ๋์ ๋ฉ์น์ ๊ทธ ๋ฑ์๊ฐ ํ์๋ ํ์ด๋ค.
์ด๋ฆ
<๋ชธ๋ฌด๊ฒ, ํค>
๋ฉ์น ๋ฑ์
A
<55, 185>
2
B
<58, 183>
2
C
<88, 186>
1
D
<60, 175>
2
E
<46, 155>
5
์ ํ์์ C๋ณด๋ค ๋ ํฐ ๋ฉ์น์ ์ฌ๋์ด ์์ผ๋ฏ๋ก C๋ 1๋ฑ์ด ๋๋ค. ๊ทธ๋ฆฌ๊ณ A, B, D ๊ฐ๊ฐ์ ๋ฉ์น๋ณด๋ค ํฐ ์ฌ๋์ C๋ฟ์ด๋ฏ๋ก ์ด๋ค์ ๋ชจ๋ 2๋ฑ์ด ๋๋ค. ๊ทธ๋ฆฌ๊ณ E๋ณด๋ค ํฐ ๋ฉ์น๋ A, B, C, D ์ด๋ ๊ฒ 4๋ช ์ด๋ฏ๋ก E์ ๋ฉ์น๋ 5๋ฑ์ด ๋๋ค. ์ ๊ฒฝ์ฐ์ 3๋ฑ๊ณผ 4๋ฑ์ ์กด์ฌํ์ง ์๋๋ค. ์ฌ๋ฌ๋ถ์ ํ์ N๋ช ์ ๋ชธ๋ฌด๊ฒ์ ํค๊ฐ ๋ด๊ธด ์ ๋ ฅ์ ์ฝ์ด์ ๊ฐ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ฅผ ๊ณ์ฐํ์ฌ ์ถ๋ ฅํด์ผ ํ๋ค.
์ ๋ ฅ
์ฒซ ์ค์๋ ์ ์ฒด ์ฌ๋์ ์ N์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ด์ด์ง๋ N๊ฐ์ ์ค์๋ ๊ฐ ์ฌ๋์ ๋ชธ๋ฌด๊ฒ์ ํค๋ฅผ ๋ํ๋ด๋ ์์ ์ ์ x์ y๊ฐ ํ๋์ ๊ณต๋ฐฑ์ ๋๊ณ ๊ฐ๊ฐ ๋ํ๋๋ค. ๋จ, 2 ≤ N ≤ 50, 10 ≤ x,y ≤ 200 ์ด๋ค.
์ถ๋ ฅ
์ฌ๋ฌ๋ถ์ ์ ๋ ฅ์ ๋์ด๋ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ฅผ ๊ตฌํด์ ๊ทธ ์์๋๋ก ์ฒซ ์ค์ ์ถ๋ ฅํด์ผ ํ๋ค. ๋จ, ๊ฐ ๋ฉ์น ๋ฑ์๋ ๊ณต๋ฐฑ๋ฌธ์๋ก ๋ถ๋ฆฌ๋์ด์ผ ํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
5
55 185
58 183
88 186
60 175
46 155
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
2 2 1 2 5
ํ์ด
์ด ๋ฌธ์ ๋ ์์ ํ๋ฅผ ๋ณด๋ฉด ์ฝ๊ฒ ์ดํดํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ๋๋ ํค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ฐฐ์ด y์ x์ ๊ฐ๊ฐ ์ ์ฅํ ํ ๋ฐ๋ณต๋ฌธ์ ๋๋ ค์ ๊ฐ๊ฐ ๋น๊ตํด์ ์์ ๋ณด๋ค ๋ฉ์น๊ฐ ํฐ ์ฌ๋์ ์๊ฐ count๋ช ์ผ๋ก ๊ตฌํ ๋ค์์ ์์ ์ ๋ฑ์๋ count + 1๋ฑ์ด๋ฏ๋ก ์ถ๋ ฅํ ๋ count + 1์ ์ถ๋ ฅํ๋๋ก ํ๋ก๊ทธ๋จ์ ์ ์ํ๋ค.
#include <stdio.h> int main(void) { int N; int count = 0; int x[50], y[50]; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d", &x[i], &y[i]); } for (int i = 0; i < N; i++) { count = 0; for (int j = 0; j < N; j++) { if (x[i] < x[j] && y[i] < y[j]) count++; } printf("%d ", count + 1); } }
๋ฐ์ํ