라이브 동영상을 DVD로 만들어 판매
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 함
한 노래를 쪼개서 두 개의 DVD에 녹화하면 안됨
M개의 DVD에 모든 동영상을 녹화
DVD의 크기(녹화 가능한 길이)를 최소로
M개의 DVD는 모두 같은 크기
첫째 줄에 자연수 N, M 입력
다음 줄에는 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 입력
DVD의 최소 용량 크기를 출력하는 프로그램 작성
입력예시)
9 3
1 2 3 4 5 6 7 8 9
출력예시)
17
내가 쓴 코드
#첫번째 코드
import sys
sys.stdin = open("input.txt", 'rt')
#입력 받기
N, M = map(int, input().split())
songs = list(map(int, input().split()))
#총 노래 길이를 만들어야하는 dvd갯수로 나눠 기준이 될 평균 dvd 길이 추출
totalDuration = sum(songs)
avgCapacity = totalDuration // M
capacity = avgCapacity
#dvd로 나누는 함수, dvd갯수를 리턴함
def makeDvds(songs, capacity):
dvds = 1
length = 0
for song in songs:
if length + song <= capacity:
length += song
else:
dvds += 1
length = song
return dvds
#m개보다 작거나 같은 수의 dvd로 나눠졌다면, capacity를 줄여가면서 최소 capacity 탐색
if makeDvds(songs, capacity) <= M:
#m개보다 많은 수가 되면 중단
while makeDvds(songs, capacity) <= M:
capacity -= 1
print(capacity+1)
#m개보다 더 많은 dvd로 나눠졌다면 capacity를 늘려야 함
else:
#m개가 되면 중단
while makeDvds(songs, capacity) > M:
capacity += 1
print(capacity)
내가 쓴 코드2
#두번째 코드
import sys
sys.stdin = open("input.txt", 'rt')
#입력 받기
N, M = map(int, input().split())
songs = list(map(int, input().split()))
#dvd로 나누는 함수, dvd갯수를 리턴함
def makeDvds(songs, capacity):
dvds = 1
length = 0
for song in songs:
if length + song <= capacity:
length += song
else:
dvds += 1
length = song
return dvds
lt = 1
rt = sum(songs)
mid = (lt + rt) // 2
#m개보다 작거나 같은 수의 dvd로 나눠 졌다면, capacity를 줄여 가면서 최소 capacity 탐색
while lt <= rt:
mid = (lt + rt) // 2
if makeDvds(songs, mid) <= M:
tmp = mid
rt = mid - 1
#m개보다 더 많은 > dvd로 나눠 졌다면 capacity를 늘려야 함
else:
lt = mid + 1
print(tmp)
모범답안
import sys
sys.stdin = open("input.txt", 'rt')
def Count(capacity):
cnt = 1
sum = 0
for x in Music:
if sum+x > capacity:
cnt += 1
sum = x
else:
sum += x
return cnt
n, m = map(int, input().split())
Music = list(map(int, input().split()))
maxx = max(Music)
lt = 1
rt = sum(Music)
res = 0
while lt <= rt:
mid = (lt + rt) // 2
if mid >= maxx and Count(mid) <= m:
res = mid
rt = mid - 1
else:
lt = mid + 1
print(res)
느낀점
1. 1씩 늘려보는게 맘에 안들었지만.. dvd용량의 최대값이 애매해서 일단 이걸로 했는데 만점 받아서 마무리했다.
2. 최대값을 모든 노래 합으로 둔거 보고 바로 이진검색으로 다시 구현해봄. 아니 total까지 구해놓고 왜 저생각을 못했지..? 하~
3. dvd갯수 세는 함수를 모범답안과 정확히 일치하게 했다.ㅎ 헤헤 물론 쉬운거지만 그래두잘해써~
4. 비록 나의 두번째 코드로 채점 결과 만점을 받았지만 모범답안에 있는 mid >= 최대dvd길이 조건이 꼭 들어가야 한다.
왜냐면 하나의 노래는 여러 dvd로 나눠지지 않아야 한다는 조건이 있기 때문!!
이진검색 정리
lt = 범위의 최솟값
rt = 범위의 최댓값
result = 최종값
while lt <= rt:
mid = (lt + rt) // 2
if 값을 줄여야 한다면:
rt = mid - 1
else 값을 늘려야 한다면:
lt = mid + 1
print(result)
if-else구문 중 답이 될 수 있는 상황에서는
res변수를 갱신(res = mid)해서 값을 담아둔다.