2343

날짜 : 2023. 4. 10

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/2343

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())
lec = list(map(int, sys.stdin.readline().split()))
total = sum(lec)

s = 0
e = int(1e9)
res = total

while s <= e:
    mid = (s + e) // 2  # 블루레이 크기
    if mid < max(lec):  # mid값이 강의 1개크기보다 작다면
        s = mid + 1  # 갱신(mic값 증가)
        continue
    cnt, tmp = 1, 0  # 블루레이 개수, 갱신하는 블루레이 길이
    for i in range(len(lec)):
        # 이전 값이랑 지금 값 더해서 mid 보다 작으면 계속 더함
        if tmp + lec[i] <= mid:
            tmp += lec[i]
        else:
            tmp = lec[i]  # mid보다 커지면 현재 lec[i]가 tmp로 들어감
            cnt += 1
    if cnt <= m:  # mid에 해당하는 개수(cnt)가 m보다 작거나 같은 경우
        e = mid - 1  # mid 값 줄임(블루레이 1개 크기 줄임)
        res = min(res, mid)
    else:
        s = mid + 1  # 아니라면 mid값 증가
print(res)

 

 

풀이

- mid라는 블루레이 1개 크기를 설정한 후 cnt, tmp라는 변수를 설정하여 for문을 돌려 해당 값들의 합을 구한 다음 이진탐색을 수행한다.

- 반복하여 더하는 과정에서 mid(임의로 설정한 블루레이 크기)보다 크다면 더이상 해당 블루레이에 들어갈 수 없기 때문에 다른 블루레이에 넣어야 한다. 그러므로 cnt를 1 늘리고, 해당 강의는 다음 블루레이에 넣는다.

- 이후 mid에 해당하는 블루레이 개수 cnt를 m과 비교한 후, 도출된 개수와 미리 설정한 개수(m)과 비교하여 cnt가 m보다 작거나 같은 경우, mid값을 늘릴 수 있기 때문에 e(end)값을 갱신하고, 반대의 경우 s(start) 값을 갱신한다.

 

* 추가

- while문 초반에 mid값이 무조건 lec(max)보다 커야 한다는 조건이 발생한다.

- 이는 블루레이가 강의 하나 이상을 수용 가능해야 한다는 조건을 붙이는 것을 의미한다. 만약 없으면 50%에서 틀림처리

반례)

3 3

9 6 13

output : 9  (if mid < max(lec): ~ continue 부분 주석처리한 경우)

answer : 13

 

알게된 점

- 하나하나 그룹을 만들어서 max 그룹과 min 그룹을 구한 다음 위치에 따라 넣는 방식으로 구현하려 했지만 3%에서 계속 TLE가 발생했다. 

- 계속 고민했는데 풀이방식이 도저히 나오지 않아 다른 사람의 소스코드를 참고했고, 이진탐색 while문에 for문을 넣어 개수를 구하는 방식으로 풀이하는 것을 확인할 수 있었다.

 

 

 

참고 사이트

- https://resilient-923.tistory.com/373

[백준]2343(파이썬) - 기타레슨