알고리즘💻/그리디

BOJ 16206번: 롤케이크

호프 2021. 1. 11. 20:00

www.acmicpc.net/problem/16206

 

16206번: 롤케이크

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

www.acmicpc.net

아이디어:

10으로 나누어 떨어지는 것부터 오름차순으로 정렬해서 잘라 나가야 최적해를 구할 수 있다.

 

import sys

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
a = [] #10으로 나누어 떨어짐
b = [] #10으로 나누어 떨어지지 않음
ans = 0

#10으로 떨어지는 수와 그렇지 않은 수를 두 개의 리스트로 나누고 오름차순으로 정렬
for i in arr:
    if (i%10==0):
        a.append(i)
    else:
        b.append(i)

a.sort()
b.sort()

for i in a:
    if (i<10): #롤케이크의 길이가 10보다 작은 경우는 패스
        continue
    if (i == 10): #롤케이크의 길이가 10이면 ans++
        ans+=1
        continue
    if (m >=(i//10-1)): #10단위로 롤케이크 자르기
        m -= (i//10-1)
        ans += i//10
    else:
        ans += m
        m = 0
for i in b:
    if (i<10):
        continue
    if (m >= i//10):
        m -= i//10
        ans += i//10
    else:
        ans += m
        break

print(ans)