[Python] 백준 16206 롤케이크 (Greedy)

📌 문제

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

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

자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
0보다 크고, x보다 작은 자연수 y를 고른다.
롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.
재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

둘째 줄에 롤케이크의 길이 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000)

출력

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

예제 입력 1

3 1
10 10 10

예제 출력 1

3

예제 입력 2

3 1
10 10 20

예제 출력 2

4

예제 입력 3

3 3
20 20 20

예제 출력 3

6

예제 입력 4

5 7
10 20 30 40 50

예제 출력 4

11

예제 입력 5

5 8
34 45 56 12 23

예제 출력 5

8

---

📌 풀이

💬 Code

import sys
input = sys.stdin.readline

n, limit = map(int, input().split())
cake = [int(i) for i in input().split()]

cakeTen = list(filter(lambda x: x % 10 == 0, cake))
cakeNotTen = list(filter(lambda x: x % 10 != 0, cake))

cnt = 0

while limit > 0:
    if cakeTen:
        if cakeTen[0] // 10 - 1 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeTen[0] // 10
            limit -= (cakeTen[0] // 10 - 1)
        del cakeTen[0]

    elif cakeNotTen:
        if cakeNotTen[0] // 10 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeNotTen[0] // 10
            limit -= cakeNotTen[0] // 10
        del cakeNotTen[0]

    else:
        break

print(cnt)

💡 Solution

케이크는 위와 같이 세가지 경우로 나눠 볼 수 있다. 사실 길이 10은 한 번도 안 자르고 케이크를 얻는다는 점에서 따로 분류했지만 30과 하나의 경우로 묶을 수 있는데,

• 길이가 10으로 나누어 떨어지는 경우: (길이÷10)-1번 자르고 (길이÷10)개 획득
• 길이가 10으로 나누어 떨어지지 않는 경우: (길이÷10)번 자르고 (길이÷10)개 획득

요렇게 나누면 된다!

cake = [int(i) for i in input().split()]

cakeTen = list(filter(lambda x: x % 10 == 0, cake))
cakeNotTen = list(filter(lambda x: x % 10 != 0, cake))

따라서 lambda를 이용해 길이가 10으로 나누어 떨어지는 케이크(cakeTen)와 떨어지지 않는 케이크(cakeNotTen)를 다른 리스트에 분류해 담아주었다.

커팅횟수는 정해져 있는데 케이크 갯수를 최대로 획득해야 하므로, 커팅횟수가 더 적은 cakeTen을 우선적으로 처리해야 한다.

cnt = 0

while limit > 0:
    # 10의 배수 케이크가 남아있으면
    if cakeTen:
        # 케이크가 길어서 많이 자를 수 있는데 커팅횟수 제한에 걸리는 경우
        if cakeTen[0] // 10 - 1 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeTen[0] // 10
            limit -= (cakeTen[0] // 10 - 1)
        del cakeTen[0]

    # 10의 배수 케이크가 없으면
    elif cakeNotTen:
        # 케이크가 길어서 많이 자를 수 있는데 커팅횟수 제한에 걸리는 경우
        if cakeNotTen[0] // 10 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeNotTen[0] // 10
            limit -= cakeNotTen[0] // 10
        del cakeNotTen[0]

    # 모든 케이크를 다 탐색했으면
    else:
        break