[백준/python] 16206 - 롤케이크

n, m = tuple(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort(key=lambda x: (x % 10, x))
result = 0
pointer = 0

while m != 0 and pointer < n:
    if arr[pointer] == 10:
        result += 1
        pointer += 1
    elif arr[pointer] % 10 == 0:
        if m <= (arr[pointer]//10) - 2:
            result += m
            pointer += 1
            m = 0
        else: 
            m = m - (arr[pointer]//10) + 1
            result += arr[pointer]//10
            pointer += 1
    else:
        if m <= (arr[pointer]//10) - 1:
            result += m
            pointer += 1
            m = 0
        else:
            m = m - (arr[pointer]//10)
            result += arr[pointer]//10
            pointer += 1
print(result)

| 알고리즘

우선 롤케이크 길이가 10의 배수인지 아닌지 확인해야 한다. 왜냐하면 10의 배수는 1회 적은 커팅으로 길이가 10인 롤케이크를 얻을 수 있기 때문이다. 예를 들면 20은 1회의 칼질로 2개의 롤케이크를 얻으나 21은 2번의 칼질로 2개의 롤케이크를 얻는다.

따라서 lambda 함수를 통해서 10의 배수를 앞에 우선 배치를 했다. 왜냐하면 이건 최대 롤케이크 수를 얻는 문제이기 때문.

 

1. 만약 롤케이크의 길이가 10이면 m(칼질 남은 횟수)을 소모하지 않고 result만 1추가해준다. 이미 완성품이기 때문.

2. 만약 롤케이크가 10의 배수라면 두가지 경우가 있는데 만약에 남은 횟수가 롤케이크의 십의 자리 -2 보다 작거나 같으면 결과는 남은 횟수 만큼 더해주고 횟수를 0으로 바꾼다. 예를 들면 남은 횟수가 2이고 롤케이크가 40이면 두번 칼질하면 끝이기 때문. 왜 -1이 아닌 -2인지는 40이 남았을 때 칼질 3번하면 4개를 얻기 때문이다. 즉, 바로 밑의 else 와 겹치지 않기 위해서 -2이다.(10의 배수는 커팅 횟수가 1회 더 적게 필요하다.)

 그리고 횟수가 -2가 아니라면 남은 횟수는 롤케이크의 10자리 보다 하나 적게 빼고 결과에 추가. 즉 40일 때 3번 일 때이다.

3. 그리고 10의 배수가 아닐 때는 십의 자리 수의 -1 보다 횟수가 적게 남았을 때, 남은 횟수만큼 결과를 더하고 횟수를 0으로. 즉 41일 때 3일 때이다.

 그게 아니라면 남은 횟수를 10의 자리 수 만큼 빼고 결과도 10의 자리 수 만큼 더한다. 예를 들면 41일 때 4일 때이다.

 

람다를 활용하자!!!

https://pearlluck.tistory.com/462

[Python] 람다식, lambda로 sorted key 정하기

 

+++

내가 좋아하는 덱을 사용한 획기적인 방법이 있어서 가져왔다.

import sys
from collections import deque
n, k = list(map(int, sys.stdin.readline().split()))
data = list(map(int, sys.stdin.readline().split()))
data = sorted(sorted(data, key=lambda x: x // 10), key= lambda x: x % 10)
data = list(map(int, data))
data = deque(data)
cnt = 0
while len(data) != 0:
    if data[0] == 10:
        cnt += 1
        data.popleft()
    elif data[0] > 10:
        if k == 0:
            break
        k -= 1
        cnt += 1
        data[0] -= 10
    elif data[0] < 10:
        data.popleft()
sys.stdout.write(f"{cnt}")

출처 : https://atgane.github.io/백준/그리디%20알고리즘/2021/01/09/백준-16206-파이썬.html

비교도 안되게 깔끔한 코드.. -10 까고 popleft 해주는 코드다.