https://www.acmicpc.net/problem/23845
| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다.
인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.
하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶다.
N개의 인형을 모두 사용하여, 마트료시카들을 판매한다고 할 때, 하령이가 올릴 수 있는 최대 수익은 얼마인가?
입력
첫째 줄에 인형의 개수 N이 주어진다. (1 ≤ N ≤ 2 × 105)
둘째 줄에 하령이가 가지고 있는 인형들의 크기를 나타내는 N개의 정수 Xi가 공백으로 구분되어 주어진다. (1 ≤ Xi ≤ 105)
출력
하령이가 올릴 수 있는 최대 수익을 출력하시오.
정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.
풀이
마트료시카의 크기는 최대 100,000입니다. 각 크기별 마트료시카의 수를 먼저 세어줍시다. 이건 O(N)에 끝낼 수 있습니다. 설명을 위해 다음 예시를 봅시다.
10
7 7 6 6 6 5 5 5 4 4 3 1
answer = 76
개수를 세어 히스토그램으로 나타내보면 뭘 해야 할지 좀 직관적으로 보입니다.
우리가 구해야 하는 부분을 선으로 나누어 표시해보겠습니다.
이렇게 연속된 한 층의 마지막 번호를 그 층의 길이에 곱하면 마트료시카의 수익이 나옵니다. 이걸 어떻게 구할거냐면, 1부터 100,000까지를 쭉 선형 탐색하면서 층을 올라갈 수 있을 때는 올라가고, 내려갈 때는 현재 층이 어디서 끝났는지, 그리고 길이가 얼마였는지를 확인해 결과에 더해나갈 겁니다. 층을 올라가며 탐색을 진행하니까 재귀가 좋아보입니다.
재귀로 구현하면 백준의 파이썬에는 재귀 제한이 좀 얕으니 제한을 넉넉하게 풀어줘야 합니다.
정답 코드
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def solution():
n = int(input())
size = list(map(int, input().split()))
count = [0] * 100001
for s in size: count[s] += 1
def find(k, s):
ret = 0
e = s
while s < 100001:
if count[s] == k:
s += 1
elif count[s] > k:
r, f = find(k + 1, s)
ret += r
s = f
else:
break
return ret + (s - 1) * (s - e), s
result, k = find(0, 0)
print(result - 10000100000) # 이거 왜인지 모르겠는데 어디선가 이 값이 계속 더해져서 마지막에 빼야 정상 출력됩니다. 뭐가 문제인지 찾아보는 것도 좋겠지만 그건 이 코드를 참고하시는 분들께 맡겨볼게요!
solution()
