BOJ 16206번: 롤케이크

www.acmicpc.net/problem/16206

16206번: 롤케이크

아이디어:

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)