[백준/정올] 3487 Copying Books - Python[파이썬]

https://jungol.co.kr/problem/1137

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

백준 사이트에선 문제가 영어로 되어 있지만 정올 사이트에선 한글로 문제를 볼 수 있다.

위 문제는 2613 숫자구슬과 비슷한 아이디어를 가지고 있는 문제로 숫자구슬을 안 풀었다면 먼저 푸는 것을 권장한다.

 

문제에서 우리가 중요하게 봐야 할 것은 "연속된 권을 베껴써야 한다" 와 "답이 두 개 이상 있다면, 첫 번째 서기공이 할 일이 가장 작은 답을 출력한다. 그래도 두 개 이상 있다면, 두 번째 서기공이 할 일이 가장 작은 답을 출력하며, 그래도 두 개 이상 있을 경우 이런 식으로 반복한다" 이다. 

 

만약 가능한 모든 페이지를 수를 하나씩 다 탐색한다면 시간이 매우 오래 걸릴 것이 명백하기에 우리는 이분탐색을 떠올려야 한다. 

여기서 숫자구슬과 동일한 아이디어가 적용되는데, 바로 이분 탐색하는 대상을 "페이지 수"로 잡아서 해당 페이지 수로 몇 명의 사람이 작업을 할 수 있는지를 계산한다. 만약 사람 수가 k보다 작거나 같다면 high를 줄이고, 많다면 low를 늘리는 방식으로 이분 탐색을 진행한다면 시간 안에 답을 도출해낼 수 있을 것이다.

 

여기서 주의할 점은 뒷 사람이 가능한 많은 책을 담당해야 하므로 뒷 사람부터 탐색해야 한다는 점과 이분탐색을 다 진행하였을 때 mid 값이 불가능한 곳을 가르키고 있지만 low > high라서 종료가 되는 경우가 존재하므로 불가능한지 가능한지 나타내는 변수가 하나 필요하다는 것이다. 

 

마지막으로 위 설명처럼 코드를 짰다면 문제점이 하나 있는데 바로 예제 중 하나인

위의 경우, 200페이지로 책을 나눌 시, 100 / 100 100 / 100 100이라서 조건에 맞지 않고 199 페이지로 책을 나눌 시 100 / 100 / 100 / 100 / 100로 조건에 맞지 않아서 절대 답을 도출해낼 수 없다.

 

이를 해결하기 위해 도출해낸 길이가 k보다 작다면 얼마만큼 작은지 변수로 저장하여 그만큼 앞에서 /를 추가하는 방식으로 코드를 추가해주면 될 것이다.

 

아래는 정답 코드로 실력의 문제로 코드가 깨끗하지 않으니 직접 한 번 짜보는 것을 권장한다.

#Copying Books

def divide(val):
    people = [] #한 사람당 작업하는 책의 수를 저장
    cnt = 0
    work = 0
    for i in range(len(book)):
        if work + book[i] <= val:
            work += book[i]
            cnt += 1
        else:
            work = book[i]
            people.append(cnt)
            cnt = 1
        if i == len(book) - 1: #마지막이면 남은 cnt를 저장
            people.append(cnt)
    return people

t = int(input())

for _ in range(t):
    m, k = map(int, input().split())
    book = list(map(int, input().split()))
    high = 0
    for i in book:
        high += i
    low = max(book)
    book = book[::-1] #역순으로 탐색

    same = 0 #최종적으로 return되는 people의 길이가 k와 동일한지 비교하는 변수로, k와 동일하지 않다면 이분 탐색을 한 번 더 진행해야 함
    while low <= high:
        mid = (low + high) // 2
        people = divide(mid)
        if len(people) <= k:
            if len(people) == k:
                same = 1
            else:
                same = 0
            high = mid - 1
        else:
            same = 0
            low = mid + 1

    if not same: 
        mid = (low + high) // 2
        people = divide(mid + 1) #이분탐색을 한 번 더 진행, +1을 하는 이유는 기존 mid값이 불가능한 값이기에 +1을 해서 가능한 값으로 바꿔주기 위함

    add = 0 #최종적인 people의 길이가 k와 비교하여 얼마나 차이가 나는지 나타내는 변수
    if len(people) < k:
        add = k - len(people)

    people = people[::-1] #people도 역순 기준으므로 거꾸로 돌려줘야 함
    book = book[::-1]
    cnt = 0
    idx = 0
    for i in range(len(book)): #출력을 위한 코드
        cnt += 1
        if cnt == people[idx]:
            print(book[i], end = ' ')
            if idx != len(people) - 1 and people[idx + 1]:
                print('/', end = ' ')
            idx += 1
            cnt = 0
        else:
            print(book[i], end = ' ')
            if add:
                print('/', end = ' ')
                add -= 1
    print()