๋ฌธ์
https://www.acmicpc.net/problem/16401
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x13๊ฐ - ์ด๋ถํ์
์๊ณ ๋ฆฌ์ฆ: ์ด๋ถ ํ์
ํ์ด
๋ช ์ ์ด ๋๋ฉด, ํ์ต์ด ์ง์๋ ์กฐ์นด๋ค์ด ๋๋ฌ ์จ๋ค. ๋ผ๋ฅผ ์ฐ๋ ์กฐ์นด๋ค์ ๋ฌ๋๊ธฐ ์ํด ํ์ต์ด๋ ๋ง๋ ๊ณผ์๋ฅผ ํ๋์ฉ ๋๋ ์ค๋ค.
์กฐ์นด๋ค์ด ๊ณผ์๋ฅผ ๋จน๋ ๋์์ ๋ผ๋ฅผ ์ฐ์ง ์๊ธฐ ๋๋ฌธ์, ํ์ต์ด๋ ์กฐ์นด๋ค์๊ฒ ์ต๋ํ ๊ธด ๊ณผ์๋ฅผ ๋๋ ์ฃผ๋ ค๊ณ ํ๋ค.
๊ทธ๋ฐ๋ฐ ๋๋ ์ค ๊ณผ์์ ๊ธธ์ด๊ฐ ํ๋๋ผ๋ ๋ค๋ฅด๋ฉด ์กฐ์นด๋ผ๋ฆฌ ์ธ์์ด ์ผ์ด๋๋ค. ๋ฐ๋ผ์ ๋ฐ๋์ ๋ชจ๋ ์กฐ์นด์๊ฒ ๊ฐ์ ๊ธธ์ด์ ๋ง๋ ๊ณผ์๋ฅผ ๋๋ ์ฃผ์ด์ผ ํ๋ค.
M๋ช ์ ์กฐ์นด๊ฐ ์๊ณ N๊ฐ์ ๊ณผ์๊ฐ ์์ ๋, ์กฐ์นด 1๋ช ์๊ฒ ์ค ์ ์๋ ๋ง๋ ๊ณผ์์ ์ต๋ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ผ.
๋จ, ๋ง๋ ๊ณผ์๋ ๊ธธ์ด์ ์๊ด์์ด ์ฌ๋ฌ ์กฐ๊ฐ์ผ๋ก ๋๋ ์ง ์ ์์ง๋ง, ๊ณผ์๋ฅผ ํ๋๋ก ํฉ์น ์๋ ์๋ค. ๋จ, ๋ง๋ ๊ณผ์์ ๊ธธ์ด๋ ์์ ์ ์์ฌ์ผ ํ๋ค.
์ฒซ์งธ ์ค์ ์กฐ์นด 1๋ช ์๊ฒ ์ค ์ ์๋ ๋ง๋ ๊ณผ์์ ์ต๋ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค.
๋จ, ๋ชจ๋ ์กฐ์นด์๊ฒ ๊ฐ์ ๊ธธ์ด์ ๋ง๋๊ณผ์๋ฅผ ๋๋ ์ค ์ ์๋ค๋ฉด, 0์ ์ถ๋ ฅํ๋ค.
๋ง๋๊ณผ์์ ๊ธธ์ด๊ฐ ๋๋๊ณ ์ ํ๋ ๊ธธ์ด๋ณด๋ค ๊ธธ๋ค๋ฉด ์๋ฅผ ์ ์์ง๋ง ํฉ์น ์ ์๋ค.
์์ 1๋ก ๋ณด๋ฉด,
3 10
1 2 3 4 5 6 7 8 9 10
# ๋ต: 8
์กฐ์นด 3๋ช ์๊ฒ ๋์ผํ ๊ธธ์ด์ ๋ง๋๊ณผ์๋ฅผ ๋๋์ด์ค์ผํ๋ฏ๋ก, 8, 9, 10 ์ 8์ ๋ง์ถฐ ์๋ฅด๋๊ฒ์ด ์ต๋๊ธธ์ด๋ค.
ํ์ง๋ง ์ ๋ต์ด ํญ์ ๋ฆฌ์คํธ ๋ด์ ์กด์ฌํ๋๊ฑด ์๋๋ค.
์๋๋ ์์ 2๋ค.
4 3
10 10 15
# ๋ต: 7
4๋ช ์๊ฒ ๋์ผํ ๊ธธ์ด๋ก ๋๋ ์ฃผ๋ ค๋ฉด 7๋งํผ์ฉ ๋ถ๋ฌ๋จ๋ ค์ผํ๋ค.
10//7 = 1
10//7 = 1
15//7 = 2
๋ฐ๋ผ์ ์ด๋ถํ์์ผ๋ก 1๋ถํฐ ๊ฐ์ฅ ํฐ ๋ง๋์ ๊ธธ์ด๋งํผ์ ํ์ํ๋ค.
๋ ๊ฐ์ ๋ํ ๋ค ๋ฐ์ผ๋ก ๋๋ mid๋ฅผ ๊ตฌํ๊ณ , ์ด ๊ธธ์ด๋งํผ ๋ง๋๊ณผ์๋ฅผ ๋ชจ๋ ๋๋๋ค.
๋๋ ๋ง๋๊ณผ์์ ๊ฐฏ์๊ฐ ์กฐ์นด์ ์ M๊ณผ ๊ฐ๊ฑฐ๋ ํฌ๋ค๋ฉด ret์ mid๋ก ๊ฐฑ์ ํ ํ start๋ฅผ mid + 1์ผ๋ก, ์๋ค๋ฉด end๋ฅผ mid - 1๋ก ๋ณ๊ฒฝ ํ ๋ค์ ํ์ํ๋ค.
start์ end๊ฐ ์ผ์นํ ๋๊น์ง ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค์ ์ต์ข ์ ์ผ๋ก ret์ ์ถ๋ ฅํ๋ค.
์ ์ฒด ํ์ด
# ๋ฉ๋ชจ๋ฆฌ: 146176KB / ์๊ฐ: 4768ms
from sys import stdin
input = stdin.readline
M, N = map(int, input().split())
snacks = sorted(map(int, input().split()))
start, end = 1, snacks[-1]
ret = 0
while start <= end:
mid = (start + end) // 2
# mid๊ธธ์ด๋งํผ ๊ณผ์๋ฅผ ์๋ผ M๊ฐ๋ก ๋ง๋ค ์ ์๋ค๋ฉด ์ฑ๊ณต
cnt = sum(snack//mid for snack in snacks)
if cnt >= M:
ret = mid
start = mid + 1
else:
end = mid - 1
print(ret)