[BOJ:16206] 롤케이크

문제

https://www.acmicpc.net/problem/16206

[

16206번: 롤케이크

오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서

www.acmicpc.net

](https://www.acmicpc.net/problem/16206)

코드

import sys
import heapq
n, m = map(int,sys.stdin.readline().rstrip().split())

cakes = list(map(int, sys.stdin.readline().rstrip().split()))

ten_multi_cake = []
not_ten_multi_cake = []
answer = 0
cur_cut_cnt = 0
total_cut_cnt = 0

for cake in cakes:
    if cake == 10:
        answer += 1
    elif cake % 10 == 0 :
        heapq.heappush(ten_multi_cake,cake)
    else:
        heapq.heappush(not_ten_multi_cake,cake)

while ten_multi_cake:
    cake = heapq.heappop(ten_multi_cake)

    cur_cut_cnt = (cake // 10) -1

    if cur_cut_cnt > m - total_cut_cnt:
        answer += m - total_cut_cnt
        total_cut_cnt += m - total_cut_cnt
        break
    elif cur_cut_cnt == m - total_cut_cnt:
        answer += (cur_cut_cnt + 1)
        total_cut_cnt += cur_cut_cnt
        break
    else:
        answer += (cur_cut_cnt + 1)
        total_cut_cnt += cur_cut_cnt

if total_cut_cnt == m:
    print(answer)
elif total_cut_cnt < m:
    while not_ten_multi_cake:
        cake = heapq.heappop(not_ten_multi_cake)
        cur_cut_cnt = cake // 10

        if cur_cut_cnt > m - total_cut_cnt:
            answer += m - total_cut_cnt
            total_cut_cnt += m - total_cut_cnt
            break
        elif cur_cut_cnt == m - total_cut_cnt:
            answer += (cur_cut_cnt)
            total_cut_cnt += cur_cut_cnt
            break
        else:
            answer += cur_cut_cnt
            total_cut_cnt += cur_cut_cnt

    print(answer)

문제해결방법

• 문제에서 구해야 하는 것은 자를 수 있는 최대 횟수 이하로 케이크를 잘라서 길이가 10인 롤케이크를 만들 수 있는 최대 개수를 구하는 것이다.
• 이때 크게 2가지 경우를 나누어서 생각 할 수 있다.
  • 케이크의 길이가 10의 배수인 경우는 자르는 횟수 + 1 개의 롤케이크가 생긴다.