[BOJ/Python] 백준 16206번 - 롤케이크

백준 #16206 롤케이크

16206번: 롤케이크

import sys
input = sys.stdin.readline

n, m = map(int, input().split())   # n: 롤케이크 개수, m: 자를 수 있는 최대 횟수
length = list(map(int, input().split()))   # 롤케이크 길이
l1 = []   # 10의 배수 리스트
l2 = []   # 10의 배수가 아닌 리스트
for l in length:
  if l < 10:
    continue
  elif l % 10 == 0:
    l1.append(l)
  else:
    l2.append(l)
l1.sort()
l2.sort()
length = l1 + l2

cut = 0   # 자른 횟수
cnt = 0   # 롤케이크 개수 최댓값

for l in length:
  while True:
    if l < 10:
      break
    elif l == 10:
      cnt += 1
      l -= 10
    else:
      l -= 10
      cnt += 1
      cut += 1
      if cut == m:
        if l == 10:
          cnt += 1
        print(cnt)
        exit(0)
  
print(cnt)

길이가 10의 배수인 롤케이크부터 잘라야 길이가 10인 롤케이크를 가장 많이 만들어낼 수 있다!

1. 입력 받은 롤케이크 길이 리스트를 10의 배수인 것과 아닌 것으로 분리하여 각각 오름차순으로 정렬한다.
2. 10의 배수 리스트가 앞에 오도록 하여 두 개의 리스트를 합친다.
3. 길이가 10인 롤케이크는 개수 + 1을 주고, 10보다 클 경우 10을 잘라 개수와 자른 횟수 + 1씩 해준다.
4. 자른 후 나머지 길이가 10보다 작을 경우 다음 롤케이크로 넘어간다.
5. 자른 횟수가 최대 횟수에 도달할 경우 자른 직후 나머지 길이가 10인 롤케이크까지 합쳐 최종 롤케이크의 개수를 출력한다.

10의 배수로 정렬하는 게 포인트! 오름차순 정렬만 생각해서 계속 틀림 😰

 

 

---

 

10의 배수로 정렬하는 거 람다식으로 쓰려다 모르겠어서 리스트 두 개 쓰는 방법으로 구현했는데 역시 방법이 있었어 ,,

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