๐ป ์ด๋ถํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด์ผ ํจ์ ์ธ์งํ๋ ๋ถ๋ถ์ด ์ ์ผ ์ค์ํ๋ค. ์ด๋ถํ์์ ํ์ด์ผ ํ๋ ๋ฌธ์ ์ ํ๋ณ๋ฒ์
โ ๋ ธ๊ฐ๋ค์ฑ์ด ๋ค์ด๊ฐ๋ค. ์ผ๋จ, ๋ด๊ฐ ์ํ๊ณ ์ ํ๋, ๋ฌด์ธ๊ฐ๋ฅผ ์ผ์ผ์ด ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ถฉ์กฑํด๊ฐ๋ฉฐ ๋น๊ตํด๊ฐ๋ ๊ณผ์ ์ด ๋ค์ด๊ฐ๋ค๋ฉด ์ด๋ถํ์ ๋๋ ๋งค๊ฐ๋ณ์ ํ์ ์ ํ์์ ๊ณ ๋ คํด๋ณด์
โก ~์๋ฅด๊ธฐ์ ๊ฐ์ ์ฃผ์ด์ง ์ต์, ์ต๋ ์ผ๋ ฌ๋ก ๋์ด๋ ์ค์์ ๋ฒ์๋ฅผ ์ค์ฌ๊ฐ๋ฉฐ ์ต์ข target(point์ผ ์๋ ์๊ณ , ์ฃผ์ด์ง ๋ฒ์์ ๊ธธ์ด์ผ ์๋ ์๋ค)์ ์ฐพ๋ ๋ฌธ์ ๋ผ๋ฉด ์ด๋ถํ์์ ๊ณ ๋ คํด๋ณด์
โ 1654 ๋์ ์๋ฅด๊ธฐ โ
import sys
input=sys.stdin.readline
K,N=map(int,input().split())
ls=[int(input())for _ in range(K)]
start,end=1,max(ls) #0,max(ls)-1 x
ans=0
while start<=end:
cnt=0
mid=(start+end)//2
for l in ls:
cnt+=(l//mid)
if cnt>=N:
ans=mid
start=mid+1
else:
end=mid-1
print(ans)
๐ป ์ด๋ถํ์ ์ ํ์์ ์๋ ๊ฒ์ด ์ค์
๐ป ์ฌ๋ฌ ๋์ ์ค ์ต๋ ๊ธธ์ด๋ฅผ max๋ก ์ก์ ๋ค, ์ ํํ 1๋ถํฐ max ์ฌ์ด์ ์ค๊ฐ ๊ธธ์ด๋ถํฐ ์์
โ ๊ฐ ๋์ ๋ณ๋ก ์ค๊ฐ๊ธธ์ด์ ๋์ ์ผ๋ก ๋๋์์ ๋์ ๊ฐ์ count
โก ๋ง์ฝ, N ์ด์์ด๋ผ๋ฉด, ์ฐพ๊ณ ์ ํ๋ ๊ฐ๊ฒฉ ๋์ ๊ธธ์ด๋ฅผ ๋ ๋๋ ค์ ์ฐพ์ ๊ฐ๋ฅ์ฑ์ด ์์ผ๋ฏ๋ก start=mid+1๋ก ๋๊ณ ํ์
(๋ฌธ์ ์ 'N๊ฐ๋ณด๋ค ๋ง์ด ๋ง๋๋ ๊ฒ๋ N๊ฐ๋ฅผ ๋ง๋๋ ๊ฒ์ ํฌํจ๋๋ค')
โข N๋ฏธ๋ง์ด๋ผ๋ฉด, ๊ฐ๊ฒฉ ๋์ ๊ธธ์ด๋ฅผ ๋ ์ค์ผ ํ์๊ฐ ์์ผ๋ฏ๋ก end=mid-1๋ก ๋๊ณ ํ์
โฃ start<=end๊ฐ ๋ ๋๊น์ง ๊ณ์ ๋ฐ๋ณต (end ์ด๊ธฐ๊ฐ์ ์ ์ด์ ์ ์ผ ๊ธด ๋์ ์ ๊ธธ์ด๋ก ์ค์ ํ๊ธฐ ๋๋ฌธ์ ๋์ ์ ๊ธธ์ด๊ฐ ์ด๋ณด๋ค ๋ ์๊ฑฐ๋ ํด ํ๋ฅ x)
โ 2512 ์์ฐ โ
import sys
input=sys.stdin.readline
N=int(input())
budgets=list(map(int,input().split()))
max_budget=int(input())
end=max(budgets)
start=1
ans=1
mid=(start+end)//2
while start<=end:
s=0
mid=(start+end)//2
for budget in budgets:
if mid<budget:s+=mid
else:s+=budget
if max_budget>=s: #need to increase the budget line
start=mid+1
ans=max(ans,mid)
else: #decrease the budget line
end=mid-1
print(ans)
๐ป ์ํ์ก์ target์ผ๋ก ์ฐพ์์ผ ํ๊ณ , ๋ ธ๊ฐ๋ค์ฑ(?)์ผ๋ก ์ผ์ผ์ด ์ต๋์์ฐ์ ์ ์ผ ๊ฐ๊น์ด ์ํ์ก์ธ์ง ์ฐพ์์ผ ํ๋ ๋ฌธ์ ์ด๊ธฐ์, (1) target ํ์ + (2) ์กฐ๊ฑด ๋ถํฉ ์ฌ๋ถ - ๋ ๊ฐ์ง ์กฐ๊ฑด์ ์ถฉ์กฑํ๋ฏ๋ก ์ด๋ถํ์ ์ ํ
๐ป ์ด๋ถํ์ ์ฃผ์์ ) ์๊ฐ ์ ์ผ ์์ ๋, ํญ์ ์์ธ ์ค์ ํ์ธํ๊ธฐ
→ ๋ง์ฝ ์ต์๊ฐ 3๊ฐ์ ์ง๋ฐฉ์ด ์กด์ฌํ๊ณ , ๊ฐ๊ฐ์ ์์ฐ์ด 1, 1, 1์ด๋ฉฐ ์ด ์์ฐ์ 3์ด๋ผ๋ฉด, ์ํ์ก์ 1๋ก default ์ค์ (์ต์ 1์ ๊ฐ์ ธ๊ฐ์ผ ํจ) (ans=1)
๐ป ์ด๋ถํ์ ์งํ → mid๋ฅผ ์ํ์ก์ผ๋ก ์ ํ๊ณ , if๋ฌธ์ผ๋ก ๋ถํฉํ๋ ์ง ํ์ธ, ์ด ๋ max_budget ์ด ์์ฐ๋ณด๋ค ์๊ฒ ๋์๋ค๋ฉด, ๋ต์ ํ๋ณด๊ฐ ๋๋ฏ๋ก ์์๋ก max(ans,mid) updateํด, ๋ต์ ํ๋ณด๊ฐ ๋ ์ ์๋ ๊ฒฐ๊ณผ ์ค ์ต๋๊ฐ์ ans ๋ณ์๋ก ์ถ๋ ฅํ๊ฒ ์ค์ !
โ 2805 ๋๋ฌด ์๋ฅด๊ธฐ โ
import sys
input=sys.stdin.readline
from collections import Counter
N,M=map(int,input().split())
trees=Counter(map(int,input().split()))
start=0
end=max(trees)
res=0
while start<=end:
total=0
mid=(start+end)//2
cut=[(h-mid)*trees[h] for h in trees if h>mid]
if sum(cut)>=M:
res=max(res,mid)
start=mid+1
else:
end=mid-1
print(res)
๐ป ๋ ธ๊ฐ๋ค์ฑ์ผ๋ก ์ฌ๋ฌ ๋ฒ ์๋ฅด๋ฉด์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฒฝ์ฐ ์ค ๋๋ฌด๋ฅผ ์๋ฅด๋ ๋์ด ์ต๋๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ → ์ด๋ถํ์ ์ฌ์ฉ!
๐ป collections์ Counter ํจ์๋ฅผ ์ฌ์ฉํ๋ฉด, Counter ํจ์๋ก ์ค๋ณตํ๋ ์ฌ๋ฌ ๋์ด๊ฐ ์์ ๊ฒฝ์ฐ ์ผ์ผ์ด if๋ฌธ์ ๋์ง ์๊ณ , ๋ฐํํ dictionary์ value๋ฅผ ๊ทธ๋๋ก ๊ณฑํ๊ธฐ๋ง ํ๋ฉด ๋๋ฏ๋ก ์ฑ๋ฅ ํฅ์
ex)
from collections import Counter
print(Counter(["hi", "hey", "hi", "hi", "hello", "hey"])) #Counter({'hi': 3, 'hey': 2, 'hello': 1})
โ 2343 ๊ธฐํ ๋ ์จ โ
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
l=list(map(int,input().split()))
start,end=max(l),sum(l)
while start<=end:
mid=(start+end)//2
grp_sum=0
cnt=1
for x in l:
grp_sum+=x
if grp_sum>mid:
grp_sum=x
cnt+=1
if cnt>M:
break
if cnt>M:
start=mid+1
else:
ans=mid
end=mid-1
print(ans)
๐ป ์๋ ๊ทธ๋ฆผ์ผ๋ก ํ ๋ฒ์ ์ค๋ช ๋๋ค.
: ๋ธ๋ฃจ๋ ์ด ํฌ๊ธฐ๊ฐ ์ปค์ง์๋ก ๋ธ๋ฃจ๋ ์ด ๊ฐ์๋ ์์์ง๋ ๋ฐ๋น๋ก ๊ด๊ณ. ans update ๊ฐ๋ฅํ ๊ตฌ๊ฐ์ ๋ธ๋ฃจ๋ ์ด ๊ฐ์๊ฐ M๋ณด๋ค ์์ ์ผ์ด์ค๋ก ๋ฌธ์ ์ '๋ธ๋ฃจ๋ ์ด์ ๊ฐ์๋ฅผ ๊ฐ๊ธ์ ์ค์ด๋ ค๊ณ ํ๋ค'๋ผ๊ณ ๋์ด์๊ธฐ ๋๋ฌธ. ๊ฐ๋ฅ๊ณผ ๋ถ๊ฐ๋ฅ ์์ญ์ ์ ํํ ๊ตฌ๋ถํด์ ans update ์ฝ๋๋ฅผ ์ ์ if๋ฌธ ๋ฃ๊ธฐ
์ถ๊ฐ๋ก start์ end๋ x๊ฐ ๋ฌถ์ํฉ์ด๋ฏ๋ก ์ต์๊ฐ ๋จ์ผ 1๊ฐ ๋ฌถ์ํฉ๋ถํฐ ์ ์ฒด ํฉ๊น์ง์ ๋ฒ์ ์ค์
'BOJ > ๐ฅ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
โ Combinatorics Intermediate I - 3 Solvedโ (1) | 2023.02.16 |
---|---|
โ Set/Map Intermediate I - 13 Solvedโ (0) | 2023.02.15 |
โ Greedy Upper-Intermediate I - 8 Solved()โ (0) | 2023.01.27 |
โ Math & Geometry Upper-Intermediate I - 5 Solvedโ (0) | 2023.01.26 |
โ Coordinate Compression Upper-Intermediate - 3 Solvedโ (0) | 2023.01.24 |
๋๊ธ