[이진 탐색] 백준 14627 파닭파닭

14627번: 파닭파닭

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

14627번: 파닭파닭

 

#1 문제 이해

• 치킨집을 운영하는 승균이는 주문받은 파닭에 일정한 길이로 파를 넣으려고 한다.
• 파닭에 파를 최대한 많이 넣어야 하며, 파닭을 만들고 남은 자투리파는 라면에 넣어 먹는다.
• 이때 라면에 넣을 자투리파의 양을 구하는 문제이다.
• 첫째줄에는 파의 개수 S(1 ≤ S ≤ 1,000,000)와 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)를 입력받는다.
• 둘째줄부터는 S줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)을 입력받는다.
• 모든 입력값과 절단기는 정수만 취급한다.
• 파닭에 들어가는 파는 여러 조각을 넣을 수 없고  하나의 통 조각으로만 허용된다. (편의상 통파라고 지칭)
• 입력값의 범위가 크기 때문에 이진 탐색을 이용한다. (선형 탐색을 이용할 경우 시간 초과가 뜰 확률이 큼)
• 파닭의 수 C를 만족시킬만큼 통파의 개수가 나와야 하므로 C 이상인 조건으로 if, else 문을 넣어 start와 end 값을 조절한다.
• 하나의 파에서 여러 개의 통파가 나올 수 있으므로 몫 연산을 이용한다.

 

#2 어려웠던 부분

틀렸습니다를 받은... 그러나 틀린 부분을 모르겠어서 스터디원들과 머리를 맞대고 고민했던 문제이다.

 

먼저 틀린 코드는 아래와 같다.

import sys

# 파의 개수(S)와 주문받은 파닭의 수(C) 입력받기
s, c = map(int, input().split())
# 파의 개수(S) 만큼 파의 길이 입력받기
pa_length = [int(sys.stdin.readline()) for i in range(s)]

# 이진 탐색을 위한 시작점&끝점 설정
# == 파 길이로 설정할 수 있는 값의 범위
start = 1
end = max(pa_length) # 가장 긴 파의 길이

# 이진 탐색 수행
result = 0
while start <= end:
    tong_pa_count = 0 # 통파 개수
    mini_pa_total = 0 # 자투리파 합계
    mid = (start + end) // 2 # 중간 길이

    # 각 파의 길이를 확인하며 자르기
    for x in pa_length:
        tong_pa_count += x // mid # 현재 길이로 자른 통파 개수 더하기
        mini_pa_total += x % mid # 현재 길이로 자르고 남은 자투리 파 더하기

    # 파닭의 수보다 통파 개수가 같거나 많은 경우: 더 길게 자르기 (오른쪽 부분 탐색)
    if tong_pa_count >= c:
      result = mini_pa_total # 최대한 길게 잘라야하므로 자투리파 합계 기록
      start = mid + 1
      
    # 파닭의 수보다 통파 개수가 적은 경우: 더 짧게 자르기 (왼쪽 부분 탐색)
    else:
        end = mid - 1

# 최적화된 값 출력
print(result)

 

구글링과 머맞을 하며 문제를 찾아보니 mini_pa_total 변수에 나머지 연산을 사용한 것이 문제였다.

예를 들어 입력값이 다음과 같다고 하자.

 

3 5
10
10
10

 

이 경우 파닭 5개에 들어가는 통파의 길이는 각 5개이며, 승균이가 먹을 자투리파의 합계는 5 (= 30 - 5*5)이다.

따라서 정답으로 자투리파의 합계 값인 5가 출력되는 것이 정상이다.

 

하지만 위 코드를 실행시키면 0이 뜨는데.......

이유는 자투리파의 합계가 통파의 길이와 일치하는 바람에 파닭의 개수를 이미 만족시켰음에도 자투리파로 취급하지 않고 통파로 넘어가버렸기 때문이다.

 

즉, 나머지 연산으로 자투리파를 구하면 위와 같은 경우를 해결할 수 없게 된다.

따라서 정답을 출력하기 위해서는 sum(pa_length) - result * c 라고 작성해 전체 파의 양에서 (최대 파의 길이 * 파닭의 수) 를 빼줘야 한다.

• 나머지 연산의 반례 주의하기

 

 

아래는 최종 코드와 풀이를 참고한 블로그이다.

https://jun-bae.tistory.com/115

[BOJ 14627 🥈2] 파닭파닭 (Python)

 

사실 여기에서 한 가지 더 이해가 어려웠던 부분은 마지막 라인 print(sum(pa_length) - end * c) 이다.

왜 start도, mid도 아닌 end 값을 사용하셨을까

 

문제에 따라 start나 end 값으로도 정답을 찾아낼 수 있지만, 일반적으로 이진 탐색에서 최적화 값을 찾기 위해서는 mid를 사용하는 것이 가장 확실하다.

문제의 주어진 조건을 만족했을 때 (통파의 개수가 파닭의 개수 이상일 때)

mid를 다른 변수 (result) 에 기록하며 점점 최적의 값이 나타날 때마다 갱신하는 것이다.

• 이진 탐색의 최적화 값을 mid에 기록하기

따라서 최종 코드에 이진 탐색 반복문을 들어가기 전 result 값을 초기화해 파의 최대 길이를 기록할 변수를 마련했다.

그리고 문제 조건을 만족할 때의 mid 값을 result에 기록해 최대 파의 길이를 얻어냈다.

 

 

그리고 마지막으로 주의할 것은 이진 탐색의 start를 0이 아닌 1로 설정하는 것이다.

문제에서 파 길이의 범위가 L(1 ≤ L ≤ 1,000,000,000) 로 언급되어 있기는 하지만, 언급이 없는 경우에도 start 값을 무조건 1로 설정하는 습관을 들여야 한다.

start = 0, end = 1 인 경우를 생각해보면 mid = (start + end) // 2 연산에서 mid가 0으로 계산되어 이후 mid로 나눌 때 ZeroDivisionError 를 만날 수 있기 때문이다.

• 이진 탐색의 start 값은 1로 설정하기

 

이번 코테 문제는 많은 관심과 도움과 사랑을 받은 금쪽이문제였던 것 같다.

도와주신 스터디원들께 감사의 큰절을 올리며 마무리

 

 

#3 최종 코드

import sys

# 파의 개수(S)와 주문받은 파닭의 수(C) 입력받기
s, c = map(int, input().split())
# 파의 개수(S) 만큼 파의 길이 입력받기
pa_length = [int(sys.stdin.readline()) for i in range(s)]

# 이진 탐색을 위한 시작점&끝점 설정
# == 파 길이로 설정할 수 있는 값의 범위
start = 1
end = max(pa_length) # 가장 긴 파의 길이

result = 0 # 파의 최대 길이
while start <= end:
    tong_pa_count = 0 # 통파 개수
    mid = (start + end) // 2 # 중간 길이

    # 파의 길이로 나누어서 개수를 구하는 과정
    for i in pa_length:
        tong_pa_count += i // mid

    # 파닭의 수보다 통파 개수가 같거나 많은 경우: 더 길게 자르기 (오른쪽 부분 탐색)
    if tong_pa_count >= c:
        result = mid # 파의 최대 길이 최적화 값 기록
        start = mid + 1

    # 파닭의 수보다 통파 개수가 적은 경우: 더 짧게 자르기 (왼쪽 부분 탐색)
    else:
        end = mid - 1

# 라면에 넣을 파의 양은
# 전체 파의 양에서 (최대 파의 길이 * 파닭의 수) 를 빼줘야한다.
print(sum(pa_length) - result * c)