๐๋ฌธ์ :
๐ํ์ด:
์ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ์งค ๋๋ ๊ฐ๋ฅํ ํฐ ์(๊ฐ์ง๊ณ ์๋ ๋ชจ๋ ๋์ ์ ํฉ / ํ์ํ ๋์ ๊ฐ์)์์ -1์ฉ ๋นผ๊ฐ๋ฉฐ ์ฐพ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์งฐ๋ค.
ํ์ง๋ง ๋ฐ๋ก ์๊ฐ์ด๊ณผ..
๊ทธ๋์ ์ด์ง ํ์์ผ๋ก ์ ๋ฐ์ฉ ๋ฒ์๋ฅผ ์ค์ฌ๊ฐ๋ฉด์ ๊ฐ๋ฅํ ๊ฐ์ฅ ํฐ ๋์ ํ ๋ง์ ๊ธธ์ด๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์งฐ๋ค.
์๊ฐ๋ณต์ก๋: O(log(N))
โ๏ธ์ฝ๋:
'''
https://www.acmicpc.net/problem/1654
๋ฌธ์ : ๋์ ์๋ฅด๊ธฐ
๋์ด๋: ์ค๋ฒ2
'''
# ์ด์ง ํ์์ผ๋ก ํ์ด์ผ ๋จ!
import sys
line_num, need = map(int, input().split())
lines = []
for _ in range(line_num):
lines.append(int(sys.stdin.readline()))
possible_max = int(sum(lines) / need)
index_min = 0
index_max = possible_max
answer = 0
while index_min <= index_max:
sum = 0
middle = (index_min + index_max) // 2
if middle == 0:
middle = 1
for i in lines:
sum += i // middle
if sum >= need:
index_min = middle + 1
else:
index_max = middle - 1
print(index_max)
๐๋งํฌ:
'๐งฉps > ๐ฅNormal' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค 2096๋ฒ] ๋ด๋ ค๊ฐ๊ธฐ (1) | 2024.10.13 |
---|---|
[๋ฐฑ์ค 18115๋ฒ] ์์ด๊ณผ ์ฟผ๋ฆฌ 38 (0) | 2024.10.01 |
[๋ฐฑ์ค 2108๋ฒ] ํต๊ณํ (0) | 2024.09.28 |
[๋ฐฑ์ค 1874๋ฒ] ์คํ ์์ด (0) | 2024.09.27 |
[๋ฐฑ์ค 1966๋ฒ] ํ๋ฆฐํฐ ํ (0) | 2024.09.26 |