[BOJ_Python] 16206_롤케이크

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

16206번: 롤케이크

내가 생각한 방식

• 예제 입력 4를 직접 해보면 알겠지만, 작은 수부터 잘라야 최대의 개수가 나오기 때문에 케이크 길이를 저장한 리스트를 오름차순으로 정렬한다.
• 케이크 길이가 10이 넘으면 10으로 자르고 10인 케이크 개수를 1개 늘린다. -> 케이크 길이가 10보다 작거나 같아질 때까지 반복
• 남은 케이크의 길이가 10이면 개수를 1개 늘린다.
• 케이크 리스트에 있는 모든 케이크에대해 반복
• 자른 횟수가 m과 같아지면 멈춘다.
• 그 때까지의 개수를 출력한다.

코드

import sys

n, m = map(int, input().split())
cake_lst = list(map(int, sys.stdin.readline().split()))

cake_lst.sort()

cnt = 0
cut = 0
for cake in cake_lst:
    while cake > 10:
        cake -= 10
        cnt += 1
        cut += 1
        if cut == m:
            break
    if cake == 10:
        cnt += 1
    if cnt == m:
        break

print(cnt)

내가 틀린 이유

• 10의 배수인 수들과 아닌 수들이 같이 입력으로 주어질 때는 크기 순으로만 정렬해야하는 것이 아니라 10의 배수들을 먼저 정렬해서 두고 그 뒤에 10의 배수가 아닌 수들을 정렬해서 둬야한다.
• 예를 들어 입력이 10 13 20이고 최대 한번만 자를 수 있다고 하면, 크기 순으로만 정렬을 하게 되면 한번 자르면 길이가 10인 케이크의 수는 2개이지만 10의 배수를 먼저 정렬하고 아닌 수들을 뒤에 정렬하게 되면 ([10, 20, 13]) 길이가 10인 케이크의 수는 3개가 되어 최대가 된다.

정답 코드

import sys

n, m = map(int, input().split())
cake_lst = list(map(int, sys.stdin.readline().split()))

# 오름차순으로 정렬하고 10의 배수인 수들이 앞으로 오게 정렬
cake_lst.sort()
cake_lst.sort(key = lambda x : x % 10)
# cake_lst.sort(key = lambda x : (x%10, x))

cnt = 0
cut = 0
for cake in cake_lst:
    while cake > 10:
        cake -= 10
        cnt += 1
        cut += 1
        if cut == m:
            break
    if cake == 10:
        cnt += 1
    if cut == m:
        break

print(cnt)

 

 이번 문제를 풀면서 테스트 케이스에 나와 있는 예시 말고도 다른 예시를 좀 더 생각해보고 풀었어야했는데 라는 아쉬움이 남은 문제였다.