์ƒˆ์†Œ์‹

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

๋ฐฑ์ค€ (boj) ํŒŒ์ด์ฌ - 1654 : ๋žœ์„  ์ž๋ฅด๊ธฐ

  • -

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

 

1654๋ฒˆ: ๋žœ์„  ์ž๋ฅด๊ธฐ

์ฒซ์งธ ์ค„์—๋Š” ์˜ค์˜์‹์ด ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ K, ๊ทธ๋ฆฌ๊ณ  ํ•„์š”ํ•œ ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. K๋Š” 1์ด์ƒ 10,000์ดํ•˜์˜ ์ •์ˆ˜์ด๊ณ , N์€ 1์ด์ƒ 1,000,000์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•ญ์ƒ K โ‰ฆ N ์ด๋‹ค. ๊ทธ ํ›„ K์ค„์— ๊ฑธ์ณ ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฐ ๋žœ์„ ์˜ ๊ธธ์ด๊ฐ€ ์„ผํ‹ฐ๋ฏธํ„ฐ ๋‹จ์œ„์˜ ์ •์ˆ˜๋กœ ์ž…๋ ฅ๋œ๋‹ค. ๋žœ์„ ์˜ ๊ธธ์ด๋Š” 231-1๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

www.acmicpc.net

 

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

 

 

 

์ •๋‹ต์ฝ”๋“œ - ํŒŒ์ด์ฌ(python)
import sys
input= sys.stdin.readline
K,N = map(int,input().split())
arr = [int(input()) for _ in range(K)]
left, right = 1, max(arr)
while(left<= right):
    mid= (left+right)//2
    sum = 0
    for i in arr:
        sum += i//mid
    
    if sum >= N:  # ์ •๋‹ต๋ณด๋‹ค ์ž˜๊ฒŒ ์ž˜๋ž์œผ๋ฉด
        left = mid+1 # ์‹œ์ž‘์ ์„ ๋ฐฉ๊ธˆ๊ฐ’ + 1๋กœ
    else : 
        right = mid-1

print(right)

 

 

Contents

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

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