[백준] 2343번 : 기타 레슨 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2343번: 기타 레슨

 

1. 문제 설명

2. 풀이과정

해당 문제에서 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 사용해야 한다는 힌트가 된다.

블루레이에 첫 레슨부터 마지막 레슨까지 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다.

모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 구할 수 있다.

 

사용할 이진 탐색의 시작 인덱스(최소 블루레이 크기)는 레슨의 최대 길이이고 종료 인덱스(최대 블루레이 크기)는 모든 레슨 길이의 합이 된다.

이진 탐색은 시작 인덱스 > 종료 인덱스가 될 때까지 수행하며 우선 중앙값을 구한다.

크기가 중앙값인 블루레이에 레슨을 차례대로 저장할 때 총 몇 장의 블루레이가 필요한지 구한다.

만약 문제의 조건에 맞게 블루레이에 모두 저장할 수 있다면 종료 인덱스를 중앙값 - 1로 변경하여 다시 탐색한다.

반면 블루레이에 모두 저장할 수 없다면 시작 인덱스를 중앙값 + 1로 변경하여 다시 탐색한다.

 

슈도코드

1. N(레슨 개수), M(블루레이 개수) 입력받기
2. T(기타 레슨 데이터 저장 리스트) 입력받기
3. start(시작 인덱스) = max(T)
4. end(종료 인덱스)  = sum(T)
5. while (start <= end):
   1. middle(중간 인덱스) 구하기
   2. sum(레슨 합) 초기화
   3. count(현재 사용한 블루레이 개수) 초기화
   4. for N의 개수만큼 반복:
      1. if (sum + 현재 레슨 시간 > 중간 인덱스): 블루레이 개수 1 증가, 레슨 합 초기화
      2. 레슨 합 = 레슨 합 + 현재 레슨 시간
   5. if (레슨 합이 0이 아니면): (블루레이가 하나 더 필요함) 블루레이 개수 1 증가
   6. if (블루레이 개수 > M): (중앙 인덱스 값으로 모든 레슨 저장 불가능) 시작 인덱스 = 중앙 인덱스 + 1
   7. else: (중앙 인덱스 값으로 모든 레슨 저장 가능) 종료 인덱스 = 중앙 인덱스 - 1
6. 시작 인덱스 출력 (최솟값)

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
T = list(map(int, sys.stdin.readline().split()))

start = max(T)
end = sum(T)

while (start <= end):
    middle = int((start + end) / 2)
    sum = 0
    count = 0

    for i in range(N):
        if (sum + T[i] > middle):
            count += 1
            sum = 0
        sum += T[i]

    if (sum != 0):
        count += 1

    if (count > M):
        start = middle + 1
    else:
        end = middle - 1

print(start)