백준 16206번: 롤케이크 (Python/Java)

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

16206번: 롤케이크

 

 

 

접근

---

최소 칼질 횟수로 길이가 10인 롤케이크를 최대한 많이 만들기 위해선 10으로 나누어 떨어지는 롤케이크를 잘라야 한다. 예를 들어 확인해보자. 길이가 30인 롤케이크와 35인 롤케이크가 있다고 하자. 길이가 30인 롤케이크는 10 / 10 / 10 두 번의 칼질을 통해 길이 10 롤케이크를 세 개 만들 수 있다. 반면 35인 롤케이크는 10 / 10 / 10 / 5 이렇게 세 번의 칼질을 통해서 길이 10 롤케이크를 세 개 만들 수 있다.

 

또한 길이가 짧은 순서대로 정렬한 뒤 칼질을 해야 한다. 만약 칼질을 2번 할 수 있고 길이가 50, 30인 롤케이크가 두 개 있다고 해보자. 만일 50을 먼저 자른다면 10 / 10 / 30으로 나누어지고 할 수 있는 칼질 수가 끝나게 된다. 이때 길이가 10인 롤케이크는 2개뿐이다. 하지만 30을 먼저 자른다고 해보자. 롤케이크는 10 / 10 / 10으로 나뉘고 칼질 수가 끝난다. 이때 길이가 10인 롤케이크는 3개가 된다.

 

우선 길이가 짧은 순서대로 정렬한 뒤, 10으로 나누어 떨어지는 것부터 잘라내기 시작하면 답을 쉽게 찾을 수 있다.

 

 

 

풀이

---

Python

cakeNum, roundNum = map(int, (input()).split())
board = list(map(int, (input()).split()))

board = sorted(board)

result = 0
checkNum = 0
resultCheck = False
for i in range(cakeNum):
    if board[i]%10 == 0:
        if (checkNum + (board[i]//10 - 1)) <= roundNum:
            result += board[i]//10
            checkNum += (board[i]//10)-1
        else:
            result += (roundNum - checkNum)
            resultCheck = True
            break

if not resultCheck:
    for i in range(cakeNum):
        if board[i]%10 != 0:
            if (checkNum + board[i]//10) <= roundNum:
                result += board[i]//10
                checkNum += (board[i]//10)
            else:
                result += (roundNum - checkNum)
                break

print(result)

 

 

 

후기

---

가끔 이상할 정도로 당연하고 작은 부분에서 헷갈리는 경우가 있다. 빵을 몇 번 나누면 몇 개로 나뉠까요 따위의 아주 기초적인 산수 문제. 조금 창피하긴 하지만... 가끔 헷갈릴 때가 있다. 이건 알고리즘 실력 문제가 아니라 내 머리 문제이니 그때그때 반성하도록 하자;;;