๐ญ ๋ฌธ์ ์ดํด
๊ตญ๊ฐ์์ฐ์ด ์ฃผ์ด์ง๊ณ , N๊ฐ์ ์ง๋ฐฉ์์ ์์ฐ ์์ฒญ์ด ์ฃผ์ด์ง ๋ ์ ํด์ง ์์ฐ ๋ด์์ ์ต๋ ์ผ๋ง๊น์ง ๋ฐฐ์ ํ ์ ์๋ ์ง ๊ณ์ฐํ๋ ๋ฌธ์ ์ด๋ค.
๋ด์ฉ์ ๋ค๋ฅด์ง๋ง ํฐ ํ์ ์ด์ ์ ํ์๋ ์ด๋ถํ์ ๋ฌธ์ ๋ค๊ณผ ๋ค๋ฅผ ๋ฐ๊ฐ ์๋ค.
์ต์ ์์ฐ์ธ 1๋ถํฐ ์ต๋ ์์ฐ์ธ max(์ง๋ฐฉ์ ์์ฐ์์ฒญ๋ค) ์ฌ์ด์์ ์ด๋ถํ์์ ํ๋ฉฐ ๊ทธ ๊ฐ์ ์ฐพ์๋ด๋ฉด ๋๋ค.
๊ตฌํ ์ธ์ด: Python
import sys
r = sys.stdin.readline
def binary_search(requests: list, budget: int) -> int:
result = 0
left = 1
right = max(requests)
while left <= right:
mid = (left + right) // 2
total_sum = sum(mid if req >= mid else req for req in requests)
if total_sum <= budget:
result = mid
left = mid + 1
else:
right = mid - 1
return result
_, bud_requests, total_bud = r(), list(map(int, r().split())), int(r())
print(binary_search(bud_requests, total_bud))
์ด๋ฌํ ์์์ ๋ค๋ฅธ ๋ฌธ์ ๋ค์์
ํ์ฌ ์ค์ ํ ์ต๋ ์ํ์ก(mid) ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ ํ ์ ์๋ ์์ฐ์ก์ ๊ณ์ฐํ๋ total_sum ๋ถ๋ถ์ ์ฐ์ฐ์ ์ค์ด๊ธฐ ์ํด์
Counter๋ฅผ ์ฌ์ฉํด ๊ฐ์ ๊ฐ์ด ์ฌ๋ฌ ๊ฐ ์กด์ฌํ๋ฉด value*key ์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์ฒ๋ฆฌํ๊ณค ํ๋ค.
๊ทธ๋ฌ๋ ์ด ๋ฌธ์ ์์ ์์ฐ ์์ฒญ์ด ์ต๋ 10,000 ๊ฐ์ด๋ค.
import sys
from collections import Counter
r = sys.stdin.readline
def binary_search(requests: Counter, budget: int) -> int:
result = 0
left = 1
right = max(requests)
while left <= right:
mid = (left + right) // 2
total_sum = sum(mid*cnt if req >= mid else req*cnt for req, cnt in requests.items())
if total_sum <= budget:
result = mid
left = mid + 1
else:
right = mid - 1
return result
_, bud_requests, total_bud = r(), Counter(map(int, r().split())), int(r())
print(binary_search(bud_requests, total_bud))
์ ๊ฒฐ๊ณผ๋ฅผ ํตํด ํ์ธํ ์ ์๋ ๊ฒ์ฒ๋ผ ์ฒ๋ฆฌํ ๊ฐ์ ์๊ฐ ๋ง์ง ์๋ค๋ฉด ์คํ๋ ค Counter๋ฅผ ์ฐ๋ ๊ฒ์ด ์๊ฐ ํจ์จ ์ธก๋ฉด์์ ๋จ์ด์ง๋ ๊ฒ์ ํ์ธํ ์ ์์๋ค.(์๊ฐ Counter, ์๋๊ฐ ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ)
๐ ๋ฐ์ดํฐ์ ์๊ฐ ๋ง๋ค๋ฉด Counter๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์คํ ์๊ฐ์ ์ค์ด๊ธฐ ์ํ ์ข์ ์๋์ด๋,
๋ฐ์ดํฐ์ ์๊ฐ ์ ๋ค๋ฉด ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ๊ณ์ฐํ๋ ๊ฒ์ด ์คํ๋ ค ์ข๋ค..!
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฑ๊ตฃ๊ธธ / ๋์ ๊ณํ๋ฒ(Dynamic-Programming) (0) | 2021.03.11 |
---|---|
[BOJ] ๋ฐฑ์ค 1535 ์๋ / ๋์ ๊ณํ๋ฒ(Dynamic-Programming) (0) | 2021.03.11 |
[BOJ] ๋ฐฑ์ค 1764 ๋ฃ๋ณด์ก / ์ด๋ถํ์ (0) | 2021.02.11 |
[BOJ] ๋ฐฑ์ค 10816 ์ซ์ ์นด๋ 2 / ์ด๋ถํ์ (0) | 2021.02.09 |
[BOJ] ๋ฐฑ์ค 1654 ๋์ ์๋ฅด๊ธฐ / ์ด๋ถํ์ (0) | 2021.02.09 |