๐ ์ถ์ฒ - 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๊ฐ ํ๋์ ๊ณต๋ฐฑ์ ๋๊ณ ๊ฐ๊ฐ ๋ํ๋๋ค.
์ถ๋ ฅ
์ฌ๋ฌ๋ถ์ ์
๋ ฅ์ ๋์ด๋ ์ฌ๋์ ๋ฉ์น ๋ฑ์๋ฅผ ๊ตฌํด์ ๊ทธ ์์๋๋ก ์ฒซ ์ค์ ์ถ๋ ฅํด์ผ ํ๋ค. ๋จ, ๊ฐ ๋ฉ์น ๋ฑ์๋ ๊ณต๋ฐฑ๋ฌธ์๋ก ๋ถ๋ฆฌ๋์ด์ผ ํ๋ค.
์ ํ
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ | |
---|---|---|
5 55 185 58 183 88 186 60 175 46 155 | 2 2 1 2 5 |
์ด ๋ฌธ์ ์ ์ ๋ ฅ์ ๋ณด๋ฉด ์๊ฐ์ด๊ณผ๋ ๋ฌธ์ ์์ ๊ฒ ๊ฐ๋ค๊ณ ์๊ฐ ๋ผ ๋ฌธ์ ๊ทธ๋๋ก ํ์ด๋ณด์๋ค.
Logic
1. ๋ชธ๋ฌด๊ฒ์ ํค๋ฅผ ์ง์ ํด๋๊ณ ๋ค๋ฅธ ์ฌ๋๋ค๊ณผ ๋น๊ต
2. ๋ง์ฝ ๋๋ณด๋ค ํค์ ๋ชธ๋ฌด๊ฒ ๋ ๋ค ํฐ ์ฌ๋์ด ์๋ค๋ฉด ์์ 1 ๋์ด๋๊ธฐ
import sys
input = sys.stdin.readline
N = int(input())
bodyList = [list(map(int, input().split())) for _ in range(N)]
# bodyList = sorted(bodyList, reverse=True)
result = []
for i in range(N):
cnt = 1
weight = bodyList[i][0]
height = bodyList[i][1]
for j in range(N):
if weight < bodyList[j][0] and height < bodyList[j][1]:
cnt += 1
result.append(cnt)
for i in range(N):
print(str(result[i]), end=" ")