16206번: 롤케이크
오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서
www.acmicpc.net
문제
오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 $A_1$, $A_2$, ..., $A_N$이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만들려고 한다.
롤케이크는 다음과 같은 과정을 통해서 자를 수 있다.
- 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
- 0보다 크고, x보다 작은 자연수 y를 고른다.
- 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.
재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 롤케이크의 개수 N과 자를 수 있는 최대 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄에 롤케이크의 길이 $A_1$, $A_2$, ..., $A_N$이 주어진다. (1 ≤ $A_i$ ≤ 1,000)
출력
재현이가 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 출력한다.
코드
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(key=lambda x: (x % 10, x)) # 10으로 나눴을 때의 나머지로 오름차순
ans = 0
for a in arr:
# 롤케이크 길이가 10의 배수
if a % 10 == 0:
cutting = a//10 - 1
if cutting > m:
ans += m
else:
ans += (cutting+1)
# 롤케이크 길이가 10의 배수 아님
else:
cutting = a//10
if cutting > m:
ans += m
else:
ans += cutting
m -= cutting
if m <= 0:
break
print(ans)
처음에는 sort를 할 때
arr.sort(key=lambda x: x % 10)
이렇게 10으로 나눈 나머지만을 기준으로 오름차순 정렬하여 틀렸다.
왜냐하면 이렇게 정렬을 하면 다음과 같은 반례가 있기 때문이다.
5 3
30 25 20 15 10
이 경우 10으로 나눈 나머지만을 기준으로 삼아 정렬하면 30 20 10 25 15 이렇게 정렬이 된다. 이렇게 되면 30에서 2번 잘라서 3조각, 20에서 1번 잘라서 2조각으로 총 5조각이 나온다. 하지만 이 예제의 경우 3번 잘라서 만들 수 있는 길이 10인 롤케이크의 최대 개수는 10, 20에서 2개, 30에서 3개로 총 6개이다. 자를 필요가 없이도 10인 케이크가 가장 앞에 와야 최대값을 얻을 수 있다.
그래서 2순위 정렬 기준으로 원소를 넣어 우선 10으로 나눈 나머지 오름차순으로 정렬하고, 그 값이 같은 경우에는 원소 자체의 값으로 오름차순 정렬을 하도록 하였다.
arr.sort(key=lambda x: (x % 10, x))
이렇게 정렬하면 위의 반례는 10 20 30 15 25 로 정렬이 되기 때문에 올바른 답 6을 구할 수 있다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 2847번 게임을 만든 동준이 (0) | 2024.01.25 |
---|---|
[Python/파이썬] 백준 16435번 스네이크버드 (0) | 2024.01.24 |
[Python/파이썬] 백준 1744번 수 묶기 (1) | 2023.12.23 |
[Python/파이썬] 백준 6137번 문자열 생성 (2) | 2023.11.27 |
[Python/파이썬] 백준 9576번 책 나눠주기 (1) | 2023.11.14 |