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

> 파이썬, 그리디 알고리즘

 

 

 

 

 

 

📖 문제 : 롤케이크 (Python)

 

 

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

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

1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
2. 0보다 크고, x보다 작은 자연수 y를 고른다.
3. 롤케이크를 잘라 길이가 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

 

 

 

 

 

내 코드

if __name__ == "__main__":
    N, M = map(int, input().split())
    cake = list(map(int, input().split()))

    ten_cake = []
    other_cake = []

    cake.sort()

    for c in cake:
        if c % 10 == 0:
            ten_cake.append(c)
        else:
            other_cake.append(c)

    count = M
    result = 0
    for t in ten_cake:
        if count <= 0:
            break

        count -= (t // 10 - 1)
        result += t // 10

    if count < 0:
        result -= -1 * count + 1
    else:
        for o in other_cake:
            if count <= 0:
                break
            count -= (o // 10)
            result += o // 10

        if count < 0:
            result -= -1 * count

    print(result)

 

 

 

 

Point ! ⭐️ 

• 재현이는 롤 케이크를 자를 수 있는 수는 한정되어있으면서,
  길이가 10인 롤케이크를 만들 수 있는 최댓값을 구하기 위해서는 자르는 롤 케이크의 순서를 정하면 된다.
  
  그 우선순위는
  (롤케이크의 길이가 10으로 나눴을 때 나머지가 0인 것들 중 낮은 값들 부터) -> (롤케이크의 길이가 10으로 나눴을 때 나머지가 0이 아닌 나머지 것들 중 낮은 값들 부터) 로 순서를 매겨 자르면 된다.
  
  예를 들어, 잘라야하는 롤케이크가 
  [89, 13, 30, 20, 10, 56] 이면,
  [10, 20, 30] -> [13, 56, 89] 순으로 자르면 되는 것이다.
  
  왜냐하면
  10으로 나눠떨어지는 수들은 길이가 10인 롤케이크를 더 많이 만들 수 있기 때문이다.
  
  20, 23을 보면
  20은 한번만 잘라도 10인 롤케이크를 2개 만들 수 있지만,
  23은 두번 잘라야 10,10,3 인 롤케이크를 만들어 길이가 10인 롤케이크를 2개를 만들 수 있는 것이다.

 

 

 

 

 

 

백준 

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

16206번: 롤케이크