[백준] 16206 롤케이크 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

16206번: 롤케이크

 

 

 

---

 

문제 접근

1. 자를 롤케이크의 크기가 10보다 작은 경우 자를 이유가 없기 때문에 넘겨준다.

 

2. 크기가 작은 롤케이크 먼저 자른다.

만약 롤케이크의 크기가 10 20 20 30 50 이 있고, 자르는 횟수 제한이 4인 경우

IF : 크기가 작은 롤케익롤케이크 먼저 자를 경우 10 사이즈의 롤케이크는 8개가 생김

IF : 크기가 큰 롤케익 먼저 자를 경우 10 사이즈의 롤케이크는 6개가 생김

 

▶ 작은 롤케익을 먼저 잘라야 더 많은 10 사이즈의 롤케이크를 얻을 수 있다.

 

3. 10의 배수와 10의 배수가 아닌 경우를 분리하여 생각해야 한다.

IF : 10의 배수인 경우 (크기 : 20)

IF : 10의 배수가 아닌 경우 (크기 : 23)

▶ 10의 배수인 20인 경우, 1번 자르는 것으로 10 / 10 두 개의 롤케이크가 생기지만,

10의 배수가 아닌 23인 경우, 1번 자르면 10 / 13 의 롤케이크가 생기기 때문에 한 번 더 잘라줘야 한다.

▶ 즉 10의 배수를 먼저 잘라야 적은 횟수로 많은 10 사이즈의 롤케이크를 얻을 수 있다.

 

4. 입력받은 롤케익 사이즈를 먼저 오름차순으로 정렬, 이후 10의 배수를 먼저 취급하기 위해 10의 배수가 앞에 오도록 한 번 더 정렬해준다.

 

---

 

문제풀이(With Python)

import sys

N,M=map(int,sys.stdin.readline().split())

roll_cake=list(map(int,sys.stdin.readline().split()))
roll_cake=sorted(roll_cake)
roll_cake=sorted(roll_cake, key=lambda x:x%10)

count=0

for cutting in roll_cake:
    if M>0:
        if cutting<10:
            continue
        elif cutting%10==0:
            temp=(cutting//10)-1
            if temp==0:
                count+=1
            else:
                if(M>=temp):
                    count+=temp+1
                    M-=temp
                else:
                    count+=M
                    break
        else:
            temp=(cutting//10)
            if (M>=temp):
                count+=temp
                M-=temp
            else:
                count+=M
                break
    else:
        break

print(count)

◇ 입력 받은 roll_cake를 sorted를 통해 내림차순으로 정렬, 이후 10의 배수를 먼저 취급하기 위해 sorted를 통해 x:x%10을 key값으로 넘긴다.

 

◇ roll_cake의 크기가 10 미만인 애들을 자를 필요가 없으니 과감하게 넘긴다

 

◇ roll_cake가 10의 배수인 경우, roll_cake ÷ 10을 몫에서 1을 빼줘야 케이크를 자른 값이 나온다. 케이크를 자른 횟수에서는 1을 빼주지만 10 사이즈의 롤케이크는 몫만큼 더해주어야 한다.

(이해가 안될 경우 본문에 문제접근 3번 그림을 확인)

 

◇ roll_cake가 10의 배수가 아닌 경우, roll_cake ÷ 10을 한몫이 케이크를 자른 횟수와 롤케이크 개수와 같다.

(이해가 안될 경우 본문에 문제접근 3번 그림을 확인)

 

◇ 자를 수 있는 횟수가 정해져 있기 때문에, 한 덩어리의 롤케이크를 10으로 전부 자를 수 있을 만큼의 횟수가 남아있는지 if문으로 먼저 검사를 거쳐야 한다.

만약 자를 수 있는 횟수가 2이고, 다음 잘라야 하는 롤케이크의 크기가 50인 경우, 2번만 자를 수 있기 때문에 마지막 남은 2번을 count에 더해 멈춰준다(break)