๋ฌธ์
https://www.acmicpc.net/problem/2805
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x13๊ฐ - ์ด๋ถํ์
์๊ณ ๋ฆฌ์ฆ: ์ด๋ถ ํ์
ํ์ด
์๊ทผ์ด๋ ๋๋ฌด M๋ฏธํฐ๊ฐ ํ์ํ๋ค. ๊ทผ์ฒ์ ๋๋ฌด๋ฅผ ๊ตฌ์ ํ ๊ณณ์ด ๋ชจ๋ ๋งํด๋ฒ๋ ธ๊ธฐ ๋๋ฌธ์, ์ ๋ถ์ ๋ฒ๋ชฉ ํ๊ฐ๋ฅผ ์์ฒญํ๋ค. ์ ๋ถ๋ ์๊ทผ์ด๋ค ์ง ๊ทผ์ฒ์ ๋๋ฌด ํ ์ค์ ๋ํ ๋ฒ๋ชฉ ํ๊ฐ๋ฅผ ๋ด์ฃผ์๊ณ , ์๊ทผ์ด๋ ์๋ก ๊ตฌ์ ํ ๋ชฉ์ฌ์ ๋จ๊ธฐ๋ฅผ ์ด์ฉํด์ ๋๋ฌด๋ฅผ ๊ตฌํ ๊ฒ์ด๋ค.
๋ชฉ์ฌ์ ๋จ๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ๋์ํ๋ค. ๋จผ์ , ์๊ทผ์ด๋ ์ ๋จ๊ธฐ์ ๋์ด H๋ฅผ ์ง์ ํด์ผ ํ๋ค. ๋์ด๋ฅผ ์ง์ ํ๋ฉด ํฑ๋ ์ด ๋ ์ผ๋ก๋ถํฐ H๋ฏธํฐ ์๋ก ์ฌ๋ผ๊ฐ๋ค. ๊ทธ ๋ค์, ํ ์ค์ ์ฐ์ํด์๋ ๋๋ฌด๋ฅผ ๋ชจ๋ ์ ๋จํด๋ฒ๋ฆฐ๋ค. ๋ฐ๋ผ์, ๋์ด๊ฐ H๋ณด๋ค ํฐ ๋๋ฌด๋ H ์์ ๋ถ๋ถ์ด ์๋ฆด ๊ฒ์ด๊ณ , ๋ฎ์ ๋๋ฌด๋ ์๋ฆฌ์ง ์์ ๊ฒ์ด๋ค.
์๋ฅผ ๋ค์ด, ํ ์ค์ ์ฐ์ํด์๋ ๋๋ฌด์ ๋์ด๊ฐ 20, 15, 10, 17์ด๋ผ๊ณ ํ์. ์๊ทผ์ด๊ฐ ๋์ด๋ฅผ 15๋ก ์ง์ ํ๋ค๋ฉด, ๋๋ฌด๋ฅผ ์๋ฅธ ๋ค์ ๋์ด๋ 15, 15, 10, 15๊ฐ ๋ ๊ฒ์ด๊ณ , ์๊ทผ์ด๋ ๊ธธ์ด๊ฐ 5์ธ ๋๋ฌด์ 2์ธ ๋๋ฌด๋ฅผ ๋ค๊ณ ์ง์ ๊ฐ ๊ฒ์ด๋ค. (์ด 7๋ฏธํฐ๋ฅผ ์ง์ ๋ค๊ณ ๊ฐ๋ค) ์ ๋จ๊ธฐ์ ์ค์ ํ ์ ์๋ ๋์ด๋ ์์ ์ ์ ๋๋ 0์ด๋ค.
์๊ทผ์ด๋ ํ๊ฒฝ์ ๋งค์ฐ ๊ด์ฌ์ด ๋ง๊ธฐ ๋๋ฌธ์, ๋๋ฌด๋ฅผ ํ์ํ ๋งํผ๋ง ์ง์ผ๋ก ๊ฐ์ ธ๊ฐ๋ ค๊ณ ํ๋ค. ์ด๋, ์ ์ด๋ M๋ฏธํฐ์ ๋๋ฌด๋ฅผ ์ง์ ๊ฐ์ ธ๊ฐ๊ธฐ ์ํด์ ์ ๋จ๊ธฐ์ ์ค์ ํ ์ ์๋ ๋์ด์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋๋ฌด๋ฅผ ์ต์ํ์ผ๋ก ์๋ผ์ผ ํ๋ ๋ฌธ์ ๋ค.
์ด๋ถํ์์ผ๋ก 0 ~ ๊ฐ์ฅ ํฐ ๋๋ฌด์ ๊ธธ์ด-1 ๋ฅผ ํ์ํ๋ฉฐ ์ต์ ์ ๊ธธ์ด๋ฅผ ์ฐพ๋๋ค.
๋ฐ๋ผ์ start = 0, end = max(trees)-1 ๊ฐ ๋๋ค.
๊ทธ๋ฆฌ๊ณ start์ end๊ฐ ํ๋์ ๊ฐ์ด ๋ ๋ ๊น์ง ํ์์ ๋ฐ๋ณตํ๋ค.
๊ฐ ํด๋ง๋ค start์ end์ ์ค๊ฐ๊ฐ mid๋ฅผ ๊ตฌํ๋ค.
mid๊ฐ ํด์๋ก ๋๋ฌด๋ ๋ ์๋ฆฌ๊ณ , ์์์๋ก ๋ ์๋ฆฐ๋ค.
๋ชจ๋ ๋๋ฌด๋ฅผ ์ฒดํฌํ๋ฉฐ ๋๋ฌด๊ฐ mid๋ณด๋ค ํด ๊ฒฝ์ฐ์๋ง mid๊ธธ์ด๋งํผ ์๋ผ๋ด๊ณ , ๋จ์ ๋๋ฌด์กฐ๊ฐ์ ์นด์ดํธํ๋ค.
1) ๋ง์ฝ ๋ชจ์ ๋๋ฌด์กฐ๊ฐ์ด M๊ฐ ์ด์์ด๋ผ๋ฉด ์ผ๋จ ๊ฐ์ ธ๊ฐ ์ ์์ผ๋ฏ๋ก ๊ฒฐ๊ณผ๊ฐ ret์ ์ ๋ฐ์ดํธํ๋ค.
ํ์ง๋ง ๋ ์๋ผ๋ด๋ฉด์ M๊ฐ๋ฅผ ๋ชจ์ ์๋ ์์ผ๋ฏ๋ก start = mid + 1๋ก ์ ๋ฐ์ดํธ ํ ๋ค์ ํ์ํ๋ค.
2) ๋ชจ์ ๋๋ฌด์กฐ๊ฐ์ด M๊ฐ๊ฐ ๋์ง ์๋๋ค๋ฉด ๋๋ฌด๋ฅผ ๋ ๋ง์ด ์๋ผ๋ด๊ธฐ ์ํด end = mid - 1๋ก ์ ๋ฐ์ดํธํ๋ค.
์ฐธ๊ณ ๋ก ์ด ๋ฌธ์ ๋ Counter ๋ชจ๋์ ์ฌ์ฉํ๋ฉด ํจ์ฌ ๋นจ๋ผ์ง๋ค.
๋ง์ฝ 10๋ฏธํฐ์ ๋๋ฌด๊ฐ 1000๊ฐ ์๋ค๋ฉด,
- ๊ธฐ์กด ์ฝ๋: 1000๊ฐ์ ๋๋ฌด๋ฅผ ๋ชจ๋ ํ์
- Counter ์ฌ์ฉ ์ฝ๋: 10๋ฏธํฐ์ ๋๋ฌด๋ฅผ ๊ณ์ฐํ ๊ฐ * 1000
์ ๊ฐ์ด ์ฐ์ฐํ์๊ฐ ์ค์ด๋ค๊ธฐ ๋๋ฌธ์ด๋ค.
์ ์ฒด ์ฝ๋ 1. ์ด๋ถํ์
# ๋ฉ๋ชจ๋ฆฌ: 150200KB / ์๊ฐ: 2112ms
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
trees = list(map(int, input().split()))
def cutting_trees(height):
return sum(tree-height for tree in trees if tree > height)
def binary_search(target):
start, end = 0, max(trees)-1
ret = 0
while start <= end:
mid = (start + end) // 2
if cutting_trees(mid) >= target:
ret = mid
start = mid + 1
else:
end = mid - 1
return ret
print(binary_search(M))
์ ์ฒด ์ฝ๋ 2. ์ด๋ถํ์ + Counter
# ๋ฉ๋ชจ๋ฆฌ: 116520KB / ์๊ฐ: 352ms
from collections import Counter
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
trees = Counter(map(int, input().split()))
def cutting_trees(height):
tmp = 0
for h, cnt in trees.items():
if h > height:
tmp += (h - height) * cnt
return tmp
def binary_search(target):
start, end = 0, max(trees)-1
ret = 0
while start <= end:
mid = (start + end) // 2
if cutting_trees(mid) >= target:
ret = mid
start = mid + 1
else:
end = mid - 1
return ret
print(binary_search(M))