알고리즘💻/그리디
BOJ 16206번: 롤케이크
호프
2021. 1. 11. 20:00
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)