백준[ 18113 | Python ] 그르다 김가놈

문제

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

풀이

문제와 같이 먼저 김밥을 조건에 맞게 K 또는 K*2로 잘라준다.
김밥을 잘라주고 나면 없어지는 김밥들이 있는데, 이 때 김밥리스트L의 사이즈를 확인하고
비어있을 경우에 조건에 맞는 김밥이 없는 것이므로 -1을 출력한다.

이후로 이분 탐색을 하는데 탐색하는 m(중간값)이 약수로 들어가기 때문에
최소 김밥 조각 수 M 보다 더 작을 경우에 m을 오히려 줄여주고,
M보다 더 큰 경우에 m을 높여주어야 한다.

구하려는 김밥조각의 길이 P를 미리 -1로 두고, 조건에 맞을 경우 계속해서 P를 갱신해주면
답을 낸다.

import sys
input = sys.stdin.readline
N, K, M = map(int, input().split()) #김밥의 개수, 꼬다리의 길이, 김밥조각의 최소개수
L = []
for _ in range(N):
    kim = int(input().rstrip())
    if kim > K*2:
        L.append(kim-(2*K))
    elif kim - K > 0 and kim < 2 * K:
        L.append(kim-K)

if len(L) == 0:
    print(-1)
    exit(0)

P = -1
l,r = 1,max(L)

while l <= r:

    m = (l+r)//2 #조각 김밥의 최대 길이
    total = sum([i//m for i in L])

    if total < M:
        r = m-1
    else:
        l = m+1
        P = m

print(P)

생각 & 정리

계속해서 나오는 오답에 정신 나갈뻔했다.
여태 풀었던 이분탐색 문제와는 다르게 약간의 기믹(나한테만) 이었던 l값과 r값의 조건 변경은
바로 알아차렸지만 의외로 김밥을 “손질된 김밥”으로 바꾸는 과정에서
김밥 길이 == 2 * K인 경우를 생각하지 못해서 너무 허탈했다.
또 문제를 ‘각’김밥 마다 최소 김밥 개수 M개를 만들어야 한다고 이해하는 바람에
너무 많은 시간을 허비했다.
문제를 있는 그대로의 조건을 가지고 풀어야하는데 ‘잘못읽는’ 실수가 잦은 것 같다.
차근차근 문제부터 제대로 이해하고, 토대로 테스트케이스 풀어본 뒤에 코드를 짜나가자.