[Python] 백준 문제풀이 - 6236번

이형래·2022년 7월 25일
0

백준문제풀이

목록 보기
31/36

백준 문제풀이 - 6236 번


링크 -> https://www.acmicpc.net/problem/6236


1. 요약 및 풀이방법

N일 동안 사용할 금액을 알고, M번만 통장에서 돈을 인출하기로 한 경우, 인출할 최소 금액 K 를 정하는 문제입니다.

일반적인 이분탐색 문제입니다.
한번 인출할 때 최소 금액을 start,
최대 금액을 end로 잡고 해당 범위를 이분탐색 합니다.

코드에서는 start = max(daily)로 두었습니다.
현재 남아있는 금액이 부족한경우 통장에 넣고 다시 인출하는데,
그때 금액이 최소 당장 사용할 금액보다는 커야 하기 때문입니다.

또한 문제에서 인출하는 횟수를 정확히 M번으로 맞추기 위해서 사용할 금액보다 돈이 남아있더라도 다시 인출하는 경우도 있다고 하는데, 이는 크게 신경쓰지 않아도 괜찮습니다.
코드에서 if count <= M 부분에 걸리게 되는데,
즉, M=5인데 총 3번만 돈을 뽑았다고 가정하면, 우선 현재 탐색하는 금액으로 생활이 가능하다는 뜻이므로, 아무때나 넣었다가 뺴서 M은 맞출 수 있기 때문입니다.


2. Code

from sys import stdin

input = stdin.readline

def main():
    N, M = map(int, input().split())
    daily = [int(input()) for _ in range(N)]

    start = max(daily)
    end = sum(daily)
    ans = 0
    while start <= end:
        mid = (start + end) // 2

        current = mid
        count = 1
        for day in daily:
            if current < day:
                current = mid
                count += 1
            current -= day

        if count <= M:
            ans = mid
            end = mid - 1
        else:
            start = mid + 1

    print(ans)

if __name__ == "__main__":
    main()

3. 학습 내용

이분탐색은 역시 탐색 시간을 많이 줄이 수 있는 방법이지만,
초기값 설정 자체도 매우 중요합니다.
채점 현황에서 다른 코드를 보니 start = min(daily)로 잡은 코드가 많이 보였습니다.
이보다는 더 작은 범위로, 문제없이 구할 수 있는 위와 같은 초기 범위 설정이 빠른 실행 시간을 가져다 주었습니다.


4. 결과

profile
머신러닝을 공부하고 있습니다. 특히 비전 분야에 관심이 많습니다.

0개의 댓글