[김태원 알고리즘] 뮤직비디오 (결정 알고리즘)

사용 언어: Python3

문제

풀이

내 풀이

from itertools import combinations

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

src, dest = 1, sum(lst)
res = []
while src<=dest:
    mid = (src+dest)//2 # DVD 용량

    # lst를 chunk에 나누기
    idx = [_ for _ in range(1,N)]
    for x in combinations(idx, M-1):
        chunk = [] # 각 DVD에 담긴 곡 길이 합
        tmp = [] # 뽑힌 인덱스 담아두기
        tmp.extend(x)

        if M-1 >=2: 
            chunk.append(sum(lst[0:tmp[0]])) # 하드코딩
            chunk.append(sum(lst[tmp[0]:tmp[1]])) # 하드코딩
            chunk.append(sum(lst[tmp[1]:len(lst)])) # 하드코딩

        if all(chunk[i]<=mid for i in range(M)):
            res.append(mid)
            dest = mid-1
            break
    else: # for~else
        src = mid+1

print(min(res)) # 최소 용량
# print(res)

• 예제 테스트케이스만 성공하고 나머지는 실패한다.

내 풀이 - 2

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

src, dest = 1, sum(lst)
res = []
while src<=dest:
    mid = (src+dest)//2 # DVD 용량
    # print('mid={}'.format(mid))
    chunk = []

    start = 0
    isContinue = True
    while isContinue:
        # chunk 나누기
        tmp = 0
        for i in range(start, len(lst)):
            if tmp+lst[i] <= mid:
                tmp+=lst[i]
                start = i+1 # 다음 원소가 start
                if i == len(lst)-1:
                    chunk.append(tmp)
                    isContinue = False
            else:
                chunk.append(tmp)
                break
        # print(chunk)
    if len(chunk) <= M: # M과 같은 것 뿐만 아니라 작은 것도 res에 저장
        res.append(mid)
        dest = mid-1
    else:
        src = mid+1

print(min(res)) # 최소 용량
# print('res={}'.format(res))

• 성공!

다른 풀이

# DVD 용량이 n일 때 lst에 있는 음악을 모두 담으려면 
# DVD 몇 장이 필요한지 계산
def calc(n, lst):
    cnt=1 # 총 몇 장의 DVD가 필요한지 (기본 1장)
    tmp=0 # 용량을 합해볼 변수
    for x in lst:
       if tmp+x > n: # 초과한 경우
           cnt+=1 # DVD 1장 추가
           tmp=x # ✅ tmp를 0으로 초기화한 뒤 x를 더했다고 생각!
       else: # 저장할 수 있는 경우
           tmp+=x
    return cnt

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

src, dest = max(lst), sum(lst) # ✅ 모든 노래가 다 들어갈 수 있도록 src는 max(lst)
res = 10000
while src<=dest:
    mid = (src+dest)//2 # DVD 용량
    if calc(mid, lst) <= M:
        res = min(res,mid) # ✅ 최솟값 업데이트
        dest = mid-1
    else:
        src = mid+1

print(res) # 최소 용량

• calc() 메서드가 핵심!
• 내가 푼 풀이보다 훨씬 깔끔하고 이해하기 좋다.

0420 - remind

# DVD 용량이 mid일 때 lst의 음악들을 모두 담으려면 DVD가 몇 장이 필요한 지 반환
def calc(mid):
    cnt = 1
    tmp = 0 # 부분합
    for x in lst:
        if tmp + x <= mid:
            tmp += x
        else:
            cnt += 1
            tmp = x
    return cnt

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

src, dest = max(lst), sum(lst)
res = 10000

while src<=dest:
    mid = (src+dest)//2

    if calc(mid) <= M:
        res = min(res, mid)
    if calc(mid) <= M:
        dest = mid-1
    else:
        src = mid+1

print(res)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기