[BOJ 23845] 백준 23845번 - 마트료시카
| INU 코드페스티벌 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23841] 데칼코마니 | |
| B | [BOJ 23842] 성냥개비 | |
| C | [BOJ 23843] 콘센트 | |
| D | [BOJ 23844] 트리 정리하기 | |
| E | [BOJ 23845] 마트료시카 | |
| G | [BOJ 23847] INU 막대기 | |
| H | [BOJ 23848] 등비수열의 합 |
1. 문제
$23845$. 마트료시카 (INU 코드페스티벌 2021 Open Contest E번)
2. 풀이
연속되는 수들을 하나의 수열로 묶고, 그 묶은 수열에서 (가장 큰 수) $\times$ (수열의 길이)의 총합을 구하는 문제이다.
단순히 내림차순으로 수열을 정렬하고 수열을 이어 붙이면, 예제 입력2에서 최적의 값을 도출해낼 수 없다. $[10,9,8], [5,4], [4]$까지 만들고 $3$을 단순하게 붙이면 $[10,9,8], [5,4], [4,3]$이 되어 정답이 $10\times 3+5\times 2+4\times 2=48<49$가 되기 때문이다.
이를 통해 해당 숫자 $x$를 $x+1$ 뒤에 붙이되, $x+1$이 속한 수열들 중 ‘각각의 수열에서 가장 큰 수’가 제일 큰 수열에 붙여야 한다는 사실을 알 수 있다.
pq[i]를 ‘가장 작은 숫자가 $i$인 수열의 가장 큰 숫자’들의 집합(자료구조: 우선순위 큐)으로 정의한다. (하나의 숫자 $x$가 ‘$i$부터 $x$까지 연속된 수가 담긴 한 개의 수열’을 의미한다.)
임의의 수 $x$가 있으면, 이 수는 $x+1$이 가장 작은 숫자인 수열에 붙일 수 있다. 이때, 위에서 보았듯이 수열들 중 ‘그 수열의 가장 큰 숫자’가 가장 큰 수열에 붙여야 최적이다. pq[x+1]에서 가장 큰 수(pq.top)가 있는 수열의 $x+1$ 뒤에 $x$를 붙이는 것이다.
그렇게 하면 이 수열의 가장 큰 수는 그대로이고, 가장 작은 수가 $x$인 수열이 된다. 따라서 본래의 pq[x+1]에서 가장 큰 수를 빼고, 그 수를 pq[x]에 집어넣어야 한다. (코드 31~33줄) 만약 어디에도 $x+1$이 없다면, $x$ 하나로 $x$가 가장 큰 수인 새로운 수열이 생겨난다. (코드 27~29줄)
모든 $X_1~X_N$에 대하여 이를 실행하고 나면, 모든 pq[i]에 들어있는 각각의 수가 하나의 수열을 나타내게 된다. pq[i]에 들어있는 수가 $x$이면, 이 수열은 $x$가 가장 큰 수이고 $i$가 가장 작은 수이므로, 마트료시카의 가격은 $Q \times T = Q \times (Q - W + 1) = x \times (x - i + 1)$ 이 된다. 이 모든 합을 구하면 정답이다.
3. 채점 결과
4. 회고
.
댓글남기기