백준 16206 롤케이크(그리디)

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

16206번: 롤케이크

문제를 읽고 그리디적으로 푸는 것이라고 생각했다.

무조껀 10의 케이크만 먹을 수 있기 때문에 10으로 나눈 몫과 나머지에 집중을 하기 시작했다.

규칙을 찾아보니까 

1. x에 대해 10으로 나눈 나머지가 있을 경우 x//10번 자르면 x//10개의 10길이 조각이 나온다.

2. x에 대해 10으로 나눈 나머지가 없을 경우 x//10 -1번 자르면 x//10개의 10길이 조각이 나온다.

 

이 2가지 규칙을 이용해서 구현을 해주면 된다.

케이크를 먼저 sort()시킨다음에 주어진 m에 대해서 차감해주면서 반복문을 진행하면 된다.

n,m = list(map(int,input().split()))
data = list(map(int,input().split()))
data.sort(key=lambda x:(x%10,x))
res = 0
#print(data)
for temp in data:
    cnt = temp//10
    if temp % 10: #나머지가 있을 때
        if cnt <= m:
            res += cnt
            m -= cnt
        else:
            res += m
            m -= m
    else: # 나머지가 없을 때
        if cnt-1 <= m:
            res += cnt
            m -= cnt-1
        else:
            res += m
            m -= m
    #print(res,m)
print(res)