BOJ 11679 - Canvas Painting (Python3)
정말로 그간 격조했다. 반쯤 블로그를 유기한 것 같은데... 현생이 너무 바빴다. 방학 때 이 블로그를 조금 더 많이 충실하게 만들 생각이다.
이번 문제는 ICPC 북서유럽 리저널인 SWERC 2015 C번 문제다. 서강대학교 PS 학회와 연합 팀연습을 했을 때 다 같이 시원하게 말린 다음 내 아이디어로 푼 문제다. (자랑 맞다.) 발상의 전환이 필요한 문제다. 이런 문제가 아니었으면 내 아이디어가 튀어나오기 전에 괴물 팀원이 구현을 끝내 놓으신다. 나는 우리 동아리 코딩 최약체다.
ICPC 리저널답게 영어로 된 문제다. 처음에는 내가 직접 번역하다가 영 귀찮아서 DeepL의 초고를 보고 내가 덧대는 방식으로 번역하기로 했다. 난 영어도 잘 못하는데...
그럼 본격적으로 풀이에 돌입해 보자.
문제
After last year’s success, Samuel W. E. R. Craft’s fame continues to grow and now he has funds for all kinds of projects that cross his mind. His newest idea involves creating arrays of canvasses with color patterns having no repeated colors.
작년에 성공을 거둔 이후 사무엘 W.E.R. 크래프트의 명성은 계속 높아지고 있으며, 이제 그의 머릿속을 스치는 모든 종류의 프로젝트를 위한 자금을 확보하고 있다. 그의 최신 아이디어는 반복되는 색상이 없는 색상 패턴으로 캔버스 배열을 만드는 것이다.
Samuel bought a set of white canvasses of varying sizes. Since painting them manually would take too much time, he devised a huge machine to automate the painting process. The painting process works as follows:
사무엘은 다양한 크기의 흰색 캔버스 세트를 구입했다. 수작업으로 그림을 그리려면 시간이 너무 많이 걸리기 때문에, 그는 그림 그리는 과정을 자동화할 수 있는 거대한 기계를 고안했다. 그 기계는 다음과 같은 방식으로 작동한다.
1. Assemble all canvasses in a line in the machine’s conveyor belt, disposed in some chosen order.
1. 모든 캔버스를 기계의 컨베이어 벨트에 특정한 순서대로 일렬로 배치한다.
2. Pick a color C and a number F (which should be less than the number of color C canvasses).
2. 색상 C와, C가 칠해진 캔버스의 수보다는 작은 수 F를 선택한다.
3. Going from left to right, all canvasses with color C are painted. The first F color C canvasses are painted with a new color X and the remaining color C canvasses are painted with a new color Y . Colors X and Y are selected by the machine, are distinct, and are different from any color used previously. The amount of ink spent in this step is equal to the sum of the sizes of the painted canvasses.
3. 왼쪽에서 오른쪽으로 이동하면서 색상 C가 있는 모든 캔버스에 페인트가 덧칠된다. 왼쪽에서부터 1번째, 2번째, ..., F번째 캔버스는 색상 X로, 나머지는 색상 Y로 칠해진다. 서로 다른 색상 X와 Y는 기계에 의해 선택되고, 이전에 사용된 모든 색상과 중복되지 않는다. 이 단계에서 사용되는 잉크의 양은 칠해진 캔버스 크기의 합과 동일하다.
4. Repeat 2. and 3. until all canvasses have distinct colors.
4. 모든 캔버스에 칠해진 색이 달라질 때까지 2. 와 3. 을 반복한다.
Consider for example that Samuel bought four canvasses of sizes 3, 5, 5 and 7. The following picture shows 2 different options for painting them.
얘를 들어서 사무엘이 3, 5, 5, 7의 크기를 가진 캔버스 4개를 구입했다고 가정해 보자. 다음 그림은 캔버스를 칠하는 두 가지 방법을 보여준다.
Given the sizes of the canvasses Samuel bought, can you help Samuel finding the minimum amount of ink the machine needs to spend in order to have all canvasses with different colors?
사무엘이 구입한 캔버스의 크기가 주어졌을 때, 사무엘의 기계가 모든 캔버스를 서로 다른 색으로 칠하게끔 하는 최소 잉크 양을 구하는 프로그램을 작성하라.
입력
The first line consists of a single integer T, the number of test cases. Each test case is composed by two lines. The first line consists of a single integer N representationg the number of canvasses. The next line contains N space separated integers representing the sizes of the canvasses.
첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 입력된다. 각각의 테스트 케이스는 두 줄로 구성되어 있다. 첫 번째 줄은 캔버스의 수를 나타내는 하나의 정수 N이, 다음 줄은 캔버스의 크기를 나타내는 공백으로 구분된 N개의 정수가 입력된다.
제한은 다음과 같다.
\(1\le T\le 100\). 테스트 케이스는 100개 이하이다.
\(\forall i, 1\le N_i \le 100\,000\). 모든 i에 대해, i번째 테스트 케이스의 캔버스 수는 100 000개 이하이다.
\(1\le s\le 100\,000\). 모든 캔버스의 크기는 100 000 이하이다.
\(1\le \sum_{i=1}^{T} N_i \le 100\,000\). 주어지는 \(N_i\)의 합은 100 000을 넘지 않는다.
예제 입력)
2
3
7 4 7
4
5 3 7 5
출력
T개의 줄에 걸쳐서, 각 테스트 케이스에 대해 모든 캔버스를 다른 색으로 칠하는 데에 소모되는 최소 잉크의 양을 출력한다.
예제 출력)
29
40
내 코드
from heapq import *
for _ in range(int(input())):
n,l = int(input()),list(map(int,input().split()))
heapify(l)
ans = 0
for i in range(n-1):
x = heappop(l)+heappop(l)
ans += x; heappush(l,x)
print(ans)
가장 중요한 발상의 전환은 페인트를 칠하는 게 아니라 역순으로, 한 겹씩 벗겨내는 것으로 생각하는 것이다.
어차피 헌 번 색칠할 때마다 현재 칠해져 있는 색깔의 수는 하나식 늘어나게 되므로, N-1번의 시행은 거쳐야 한다. 그렇다면 각 단계마다 최소의 잉크를 소모하도록 할 수 있을 것이다. 역순으로 바꾼다고 해도 이 판단은 변하지 않는다. 매번, 가장 작은 잉크를 소모하도록 해야 한다는 것.
이걸 거꾸로 생각한다면 처음에 모두 다른 색으로 칠해져 있는 N개의 캔버스에 A색과 B색으로 칠해져 있는 캔버스를 C색으로 덧칠하는 시행을 N-1번 하면 될 것이다. 어떻게? 소모하는 잉크가 가장 적게. 가장 크기가 작은 두 개의 캔버스를 합치는 방식으로.
캔버스의 크기를 모조리 때려박은 우선순위 큐(heapq)에 모조리 때려박는다. 가장 크기가 작은 두 개의 캔버스를 합치는 방식은 가장 작은 두 개의 원소를 빼낸 다음, 그 둘을 더한 값을 우선순위 큐에 다시 집어넣는 방법으로 구현 가능하다.
이 때 소모된 잉크의 양은 우선순위 큐에 집어넣어지는 바로 그 값이니, 새로 ans라는 변수를 만들어 그때그때 더해주면 어렵지 않게 답을 얻을 수 있다.
이로서 11679번의 풀이를 마친다.
