패스트캠퍼스 환급챌린지 6일차 : 네카라쿠배 취업 끝장내는 파이썬 코딩테스트 마스터

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.

 

 

Chatper 2. 3강 이분 탐색 예제 2 

문제를 풀어보자

 

 

 

 

2343번: 기타 레슨

 

음 시도했지만 못 풀었다 ㅋㅎ.. 강사님 풀이 열심히 보겠습니다 ㅠㅠ

아니 근데 하나 풀이 보고 연습하고 하는데 거의 50분이나 소요됐다. 실화냐.. 

 

 

 

강사님 답

N, M = map(int, input().split())
running_time = list(map(int, input().split()))

# 이분 탐색
left = max(running_time)
right = sum(running_time)
answer = -1

while left <= right:
    middle = (left + right) // 2

    blueray_num = 1
    remain = middle

    for i in running_time:
        if remain < i:
            blueray_num += 1
            remain = middle
        remain -= i

    if blueray_num <= M:
        answer = middle
        right = middle - 1
    else:
        left = middle + 1

print(answer)

 

 

풀이

이분 탐색을 할거니 탐색하려는 값과 탐색 범위를 먼저 정해야 한다. 

• 탐색하려는 값: 블루레이의 용량
• 탐색 범위: [영상길이의 최댓값, 영상길이의 총 합]

1. [9, 45] 부터 시작. 

2. 이진 탐색이니 중간값인 27일 때, 모든 영상이 블루레이 3개에 담길 수 있는지 판별. 

3. 다 담겨진다. 그렇다면 [9, 27]로 탐색 시작

4. [9, 18] 탐색 시작.

5. 중간 값인 13일 때 3개의 블루레이에 담을 수 없다.

6. [14, 18] 탐색 시작. 

7. 중간 값 16으로 불가 --> [17, 18] 범위 설정

8. 17 가능. 정답

 

 

내가 못 한 부분

1. 잘못된 탐색 범위 선정

아! 나는 탐색 범위를 [1, 영상 길이의 총 합] 으로 잡았는데, 생각해보니 최댓값이 맞다. 영상 길이가 9분인데 블루레이 용량이 1이면 9분짜리 영상은 아예 못 담는 다는 뜻이니까. 

 

2. 잘못된 문제 이해

ㅋㅎ... 이런 스타일 문제 여러 번 보다 보면 적응될 거야.. 

 

3. 찾은 블루레이 용량 값을 기준으로 3개의 블루레이에 영상을 담는 부분 구현

이거 막 리스트 pop하고 이랬는데.. 강사님 풀이보니 단순하게 구현가능했다. 응.. 또 배워.. 배움의 연속인 나날.. 즐거워..

 

 

https://abit.ly/lisbva

#패스트캠퍼스 #환급챌린지 #패스트캠퍼스후기 #습관형성 #직장인자기계발 #오공완