๐ Problem Solving/Baekjoon
https://www.acmicpc.net/problem/2343
n, m = map(int, input().split())
data = list(map(int, input().split()))
left, right = max(data), sum(data)
while left <= right:
mid = (left + right) // 2
cnt = 0
temp = 0
for i in range(n):
if temp + data[i] > mid:
cnt += 1
temp = 0
temp += data[i]
cnt += 1 if temp else 0
if cnt <= m:
right = mid - 1
else:
left = mid + 1
print(left)
ํด์ค
์ค๋๋ง์ ์ด๋ถํ์ ๋ฌธ์ ๋ฅผ ํ์๋๋ฐ ์ด ๋ฌธ์ ์ ๊ฝค๋ ์๊ฐ์ ์์๋ค..๐ฑ
๋ค๋ฅธ ๋ฌธ์ ๋ค์ ๋นํด ์๊ฐ์ ๋ ์ด๋งํผ ํ์คํ ์์๊ฐ๋ค.
๋ธ๋ฃจ๋ ์ด์ ์ต๋ ๊ธธ์ด๋ ๋ฆฌ์คํธ์ ํฉ, ์ต์ ๊ธธ์ด๋ ๋ฆฌ์คํธ์ ์ต๋๊ฐ์ด๋ค.
๋ฆฌ์คํธ์ 1 ~ 9๊น์ง ์ ์ฅ๋์ด์๋ค๋ฉด ๊ฐ๊ฐ ์ต๋, ์ต์ ๊ธธ์ด๋ 45์ 9๊ฐ ๋๋ค.
์ด ๋ ๋ธ๋ฃจ๋ ์ด์ ๋ค์ด๊ฐ ์ ์๋ ๋ ์จ์ 1๊ฐ, 9๊ฐ๊ฐ ๋ ์ ์๋ค.
์์์ ์ธ๊ธํ ๋๋ก left์ right๋ฅผ ์ค์ ํด์ฃผ๊ณ ๋ฐ๋ณต๋ฌธ์ ํตํด ์ป์ด์ง ๋ฆฌ์คํธ์ ํฉ์ด mid๋ณด๋ค ์ปค์ง๋ฉด cnt(๋ธ๋ฃจ๋ ์ด ๊ฐ์)๋ฅผ 1์ฉ ์ฆ๊ฐ์ํจ๋ค. ์ด๋ ๊ฒ ์ป์ ๋ธ๋ฃจ๋ ์ด ๊ฐ์๊ฐ m๋ณด๋ค ์์ผ๋ฉด right๋ฅผ ์ค์ฌ์ฃผ๊ณ , m๋ณด๋ค ํฌ๋ค๋ฉด left๋ฅผ ๋๋ ค์ค๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-17626] Four Squares / Python (1) | 2021.05.18 |
---|---|
[๋ฐฑ์ค-2776] ์๊ธฐ์ / Python (0) | 2021.05.18 |
[๋ฐฑ์ค-2822] ์ ์ ๊ณ์ฐ / Python (0) | 2021.05.18 |
[๋ฐฑ์ค-11728] ๋ฐฐ์ด ํฉ์น๊ธฐ / Python (0) | 2021.05.18 |
[๋ฐฑ์ค-11656] ์ ๋ฏธ์ฌ ๋ฐฐ์ด / Python (0) | 2021.05.18 |