์ƒˆ์†Œ์‹

๐Ÿงฎ ์•Œ๊ณ ๋ฆฌ์ฆ˜/-- ๋ฐฑ์ค€ (BOJ) - Python

๋ฐฑ์ค€ (boj) ํŒŒ์ด์ฌ - 2805 : ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ

  • -

๋ฌธ์ œ ๋งํฌ : https://www.acmicpc.net/problem/2805

 

2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ

๋ฌธ์ œ ์ƒ๊ทผ์ด๋Š” ๋‚˜๋ฌด M๋ฏธํ„ฐ๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๊ทผ์ฒ˜์— ๋‚˜๋ฌด๋ฅผ ๊ตฌ์ž…ํ•  ๊ณณ์ด ๋ชจ๋‘ ๋งํ•ด๋ฒ„๋ ธ๊ธฐ ๋•Œ๋ฌธ์—, ์ •๋ถ€์— ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ์š”์ฒญํ–ˆ๋‹ค. ์ •๋ถ€๋Š” ์ƒ๊ทผ์ด๋„ค ์ง‘ ๊ทผ์ฒ˜์˜ ๋‚˜๋ฌด ํ•œ ์ค„์— ๋Œ€ํ•œ ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ๋‚ด์ฃผ์—ˆ๊ณ , ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ ๊ตฌ์ž…ํ•œ ๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋ฅผ ์ด์šฉํ•ด์„œ ๋‚˜๋ฌด๋ฅผ ๊ตฌํ• ๊ฒƒ์ด๋‹ค. ๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋™์ž‘ํ•œ๋‹ค. ๋จผ์ €, ์ƒ๊ทผ์ด๋Š” ์ ˆ๋‹จ๊ธฐ์— ๋†’์ด H๋ฅผ ์ง€์ •ํ•ด์•ผ ํ•œ๋‹ค. ๋†’์ด๋ฅผ ์ง€์ •ํ•˜๋ฉด ํ†ฑ๋‚ ์ด ๋•…์œผ๋กœ๋ถ€ํ„ฐ H๋ฏธํ„ฐ ์œ„๋กœ ์˜ฌ๋ผ๊ฐ„๋‹ค. ๊ทธ ๋‹ค์Œ, ํ•œ ์ค„์— ์—ฐ์†ํ•ด์žˆ๋Š” ๋‚˜๋ฌด๋ฅผ ๋ชจ๋‘ ์ ˆ๋‹จํ•ด๋ฒ„๋ฆฐ๋‹ค. ๋”ฐ

www.acmicpc.net

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜ : ์ด๋ถ„ํƒ์ƒ‰

 

 

๋ฌธ์ œ ์ œ์ถœ์‹œ, python์œผ๋กœ๋Š” ์•„๋ฌด๋ฆฌ ํ•ด๋„ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค. ์–ด์ฉ” ์ˆ˜ ์—†์ด pypy๋กœ ์ œ์ถœํ–ˆ๋Š”๋ฐ ๋‚˜์ค‘์— ํ•œ๋ฒˆ ๋‹ค์‹œํ•ด๋ด์•ผ๊ฒ ๋‹ค..

์ •๋‹ต์ฝ”๋“œ -python (pypy๋กœ ์ œ์ถœ)
N, M = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
left = 1   #์ œ์ผ ๋งŽ์ด ๊ฐ€์ ธ๊ฐ€๋Š” ๊ฒฝ์šฐ.
right = max(arr)  #์ œ์ผ ์กฐ๊ธˆ ๊ฐ€์ ธ๊ฐ€๋Š” ๊ฒฝ์šฐ.
answer= -1
while(left<=right):
    mid = (left+right)//2
    sum = 0
    for i in arr :
        if i-mid >= 0 : sum += i-mid
    if sum>=M :
        left = mid +1
    else :
        right = mid -1
print(right)
Contents

ํฌ์ŠคํŒ… ์ฃผ์†Œ๋ฅผ ๋ณต์‚ฌํ–ˆ์Šต๋‹ˆ๋‹ค

์ด ๊ธ€์ด ๋„์›€์ด ๋˜์—ˆ๋‹ค๋ฉด ๊ณต๊ฐ ๋ถ€ํƒ๋“œ๋ฆฝ๋‹ˆ๋‹ค.