[BAEKJOON/Python] no.16401 과자 나눠주기 | 이진 탐색

문제

---

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

16401번: 과자 나눠주기

 

 

1차 풀이 : 구글링ㅎ

---

👉🏻도대체가 어떻게 풀어야 하는지 모르겠어서 1시간 고민하고 구글링을 해보았다..ㅎㅎ

from sys import stdin
input = stdin.readline

children_count, snack_count = map(int, input().split())
snacks = list(map(int, input().split()))

snacks.sort(reverse=True)
result = 0

start = 0
end = max(snacks)

while start <= end:
    total = 0
    mid = (start + end) // 2

    if mid == 0:
        break
        
    for snack in snacks:
        if snack >= mid:
            total += (snack // mid)
        else:
            break

    if total >= children_count:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

👉🏻일단 전체코드는 이렇다..ㅎ

from sys import stdin
input = stdin.readline

👉🏻속도의 향상을 위해 stdin을 사용한다.

children_count, snack_count = map(int, input().split())
snacks = list(map(int, input().split()))

snacks.sort(reverse=True)
result = 0

👉🏻각 입력값들을 변수에 넣어주고 과자 길이를 담은 리스트인 snacks는 거꾸로 정렬(큰 값이 앞으로 오도록)한다. 마지막으로 답을 반환할 result 변수를 만든다.

start = 0
end = max(snacks)

while start <= end:
    total = 0
    mid = (start + end) // 2

    if mid == 0:
        break

    for snack in snacks:
        if snack >= mid:
            total += (snack // mid)
        else:
            break

    if total >= children_count:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

👉🏻코드를 보기전에! 일단 mid를 조카들에게 나누어 줄 과자의 크기라고 생각하면 편하다! 그리고 total을 mid의 길이로 과자를 나누어주었을 때 받을 수 있는 사람의 수라고 생각하면 편하다.

• start를 0으로 end를 가장 긴 과자의 길이로 설정한다.
• snacks의 과자를 for문에 돌리면서 과자의 길이와 mid(조카들에게 나누어 줄 과자의 크기)의 크기를 비교한다.
  • 과자의 길이가 길면 (snack // mid)명에게 과자를 나누어 줄 수 있기 때문에 이 값을 total(mid의 길이로 과자를 나누어주었을 때 받을 수 있는 사람의 수)에 더한다.
  • 과자가 더 짧으면 break을 통해 for문을 탈출한다. snacks 리스트는 길이가 긴 순으로 정렬되어 있기 때문에 이후의 과자도 다 짧기 때문에 그냥 탈출해도 된다.
• total(mid의 길이로 과자를 나누어주었을 때 받을 수 있는 사람의 수)이 조카의 수보다 같거나 크면 mid보다 더 긴 길이로 과자를 줄 여지가 있기 때문에 start를 mid + 1로 변경하고 result에 mid값을 저장한다.
• total이 조카의 수보다 작으면 mid보다 더 짧은 길이로 과자를 나누어주어야 하기 때문에 end를 mid - 1로 변경한다.

👉🏻내겐 조금 어려운 문제라..구글링으로 풀었다🥲

🐰아참! pypy를 써야 하더라...

👉🏻문제점은 아래와 같다.