[Python/파이썬] 백준 16206번 롤케이크

16206번: 롤케이크

 

문제

오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 $A_1$, $A_2$, ..., $A_N$이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만들려고 한다.

롤케이크는 다음과 같은 과정을 통해서 자를 수 있다.

1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
2. 0보다 크고, x보다 작은 자연수 y를 고른다.
3. 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.

재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤케이크의 개수 N과 자를 수 있는 최대 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄에 롤케이크의 길이 $A_1$, $A_2$, ..., $A_N$이 주어진다. (1 ≤ $A_i$ ≤ 1,000)

출력

재현이가 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 출력한다.

코드

n, m = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort(key=lambda x: (x % 10, x))  # 10으로 나눴을 때의 나머지로 오름차순

ans = 0
for a in arr:
    # 롤케이크 길이가 10의 배수
    if a % 10 == 0:
        cutting = a//10 - 1
        if cutting > m:
            ans += m
        else:
            ans += (cutting+1)
    # 롤케이크 길이가 10의 배수 아님
    else:
        cutting = a//10
        if cutting > m:
            ans += m
        else:
            ans += cutting
    m -= cutting
    if m <= 0:
        break
print(ans)

처음에는 sort를 할 때

arr.sort(key=lambda x: x % 10)

이렇게 10으로 나눈 나머지만을 기준으로 오름차순 정렬하여 틀렸다.

왜냐하면 이렇게 정렬을 하면 다음과 같은 반례가 있기 때문이다.

 

5 3

30 25 20 15 10

 

이 경우 10으로 나눈 나머지만을 기준으로 삼아 정렬하면 30 20 10 25 15 이렇게 정렬이 된다. 이렇게 되면 30에서 2번 잘라서 3조각, 20에서 1번 잘라서 2조각으로 총 5조각이 나온다. 하지만 이 예제의 경우 3번 잘라서 만들 수 있는 길이 10인 롤케이크의 최대 개수는 10, 20에서 2개, 30에서 3개로 총 6개이다. 자를 필요가 없이도 10인 케이크가 가장 앞에 와야 최대값을 얻을 수 있다. 

그래서 2순위 정렬 기준으로 원소를 넣어 우선 10으로 나눈 나머지 오름차순으로 정렬하고, 그 값이 같은 경우에는 원소 자체의 값으로 오름차순 정렬을 하도록 하였다.

arr.sort(key=lambda x: (x % 10, x))

이렇게 정렬하면 위의 반례는 10 20 30 15 25 로 정렬이 되기 때문에 올바른 답 6을 구할 수 있다.