๊ฐ๋ฅ๋ฒ๋ ํ ๋ง๋ฆฌ๊ฐ ์ฅ์ ๋ฌผ(์์, ์ข ์ ์)์ผ๋ก ๊ฐ๋์ฐฌ ๋๊ตด์ ๋ค์ด๊ฐ๋ค. ๋๊ตด์ ๊ธธ์ด๋ N๋ฏธํฐ์ด๊ณ ๋์ด๋ H๋ฏธํฐ์ด๋ค. (N์ ์ง์), ์ฒซ ์ฅ์ ๋ฌผ์ ํญ์ ์์์ด๊ณ ๊ทธ ๋ค์์๋ ์ข ์ ์๊ณผ ์์์ด ๋ฒ๊ฐ์๊ฐ๋ฉฐ ๋ฑ์ฅํ๋ค.
๊ฐ๋ฅ๋ฒ๋ ๋ ์ฅ์ ๋ฌผ์ ํผํ์ง ์๊ณ ์ผ์ง์ ์ผ๋ก ์ง๋๊ฐ๋ฉฐ ๋ชจ๋ ์ฅ์ ๋ฌผ์ ํ๊ดดํ๋ค.
๊ฒฐ๊ณผ์ ์ผ๋ก ๋๊ตด ํฌ๊ธฐ, ๋์ด, ๋ชจ๋ ์ฅ์ ๋ฌผ์ ํฌ๊ธฐ๊ฐ ์ฃผ์ด์ง ๋, ๊ฐ๋ฅ๋ฒ๋ ๊ฐ ํ๊ดดํด์ผ ํ๋ ์ฅ์ ๋ฌผ์ ์ต์๊ฐ๊ณผ ๊ทธ๋ฌํ ๊ตฌ๊ฐ์ด ์ด ๋ช ๊ฐ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ ๋ฌธ์ .
import sys
input = sys.stdin.readline
n, h = map(int, input().split())
seok = []
jong = []
for i in range(n):
if i % 2 == 0:
seok.append(int(input()))
else:
jong.append(int(input()))
seok.sort()
jong.sort()
def binary_search(array, target):
start, end = 0, len(array)
while start < end:
mid = (start + end-1) // 2
if array[mid] <= target:
start = mid + 1
else:
end = mid
return len(array) - end
answer = n
cnt = 0
for i in range(1, h+1):
seok_cnt = binary_search(seok, i-1)
jong_cnt = binary_search(jong, h-i)
if answer > seok_cnt + jong_cnt:
answer = seok_cnt + jong_cnt
cnt = 1
elif answer == seok_cnt + jong_cnt:
cnt += 1
print(answer, cnt)
< ํด์ค >
๋์ ํฉ์ด ์๋ ์ด๋ถํ์ ๋ฐฉ์์ผ๋ก ํด๊ฒฐํ๊ธฐ ์ํด ์๊ฐ ํฌ์๋ฅผ ์ค๋ ํ ๋ฌธ์ .
๋ ์ฌ๋ฆฐ ์์ด๋์ด๋ก๋ ์์์ ๋ฐ์์ ์์, ์ข ์ ์์ ์์์ ์์ํ๊ธฐ์ ์ด๋ฅผ ๊ณ ๋ คํด์ค์ผ ํ๋ค.
๊ฐ๋ฅ๋ฒ๋ ๊ฐ n๊ธธ์ด์ ๋๊ตด์ ํต๊ณผํ๋๋ฐ ์์ด ๋ฐฉ๋ฒ์ ์ด h๊ฐ๋ค.
๊ทธ๋ ๊ธฐ์ h๋ฒ ๋งํผ์ loop๋ฅผ ๋๋ฉฐ ์์, ์ข ์ ์์ upper bound๋ฅผ ํ์ธํด์ผ ํ๋๋ฐ, ์์๊ณผ ์ข ์ ์์ ์์ ์์น๊ฐ ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ ์ด๋ฅผ ๋ง์ถฐ์ค ํ์๊ฐ ์๋ค.
h๋ฒ ๋ฃจํ๋ฅผ ๋๋ ค ๊ฐ ์์, ์ข ์ ์์ upper bound๋ฅผ ๊ตฌํด ํต๊ณผํ๋ ์ฅ์ ๋ฌผ ๊ฐ์๋ฅผ ๊ตฌํด์ฃผ๊ณ ์ด๋ฅผ ๋น๊ตํด๊ฐ๋ฉฐ answer (์ฅ์ ๋ฌผ ์ต์ ํต๊ณผ ๊ฐ์), cnt(h๋ฒ ์ค answer ๋งํผ ํต๊ณผํ๋ ํ์)๋ฅผ ๊ตฌํ๋ค.