[ BOJ ] 23845 : 마트료시카 ( GOLD 3 ) / Python

문제

인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다.

인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.

하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶다.

N개의 인형을 모두 사용하여, 마트료시카들을 판매한다고 할 때, 하령이가 올릴 수 있는 최대 수익은 얼마인가?

입력

첫째 줄에 인형의 개수 N이 주어진다. (1 ≤ N ≤ 2 × 10^5)

둘째 줄에 하령이가 가지고 있는 인형들의 크기를 나타내는 N개의 정수 Xi가 공백으로 구분되어 주어진다. (1 ≤ Xi ≤ 10^5)

출력

하령이가 올릴 수 있는 최대 수익을 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

풀이 과정

(Q - W + 1 = T) 를 만족하는 인형의 집합은 연속된 수열이다.

마트료시카를 하나씩 파는 것보다 최대한 한 번에 많이 파는 것이 이득이므로, 연속된 수열을 지속적으로 제거하면서 Q x T를 더해간다.

 

먼저 수열에서 특정 수가 몇 번 등장했는지 카운트하고, 오름차순으로 정렬된 수들(공통 부분 없이)을 하나씩 세면서 연속 부분이 있다면 이 연속된 수열을 1개씩 판매한다. (1 2 3 5 8 9 10 -> (1 2 3) 5 (8 9 10))

연속된 수열을 판매해도 아직 남아있는 수가 있을 수 있으므로 이 점에 유의한다. (1 2 2 3 -> (1 2 3) 2 -> 2)

연속된 수열에 포함되지 않는 수는 하나씩만 팔아야 하므로, 연속된 수열에 포함되지 않는 수가 여러 번 등장했다면 (ex. 1 2 3 5 5 5 5 5) 한번에 제거한다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())

# 연속된 수열 지속 제거하기
arr = list(map(int, input().rstrip().split()))
now = {}
for a in arr:
    if not now.get(a): now[a] = 1
    else: now[a] += 1

now = list(now.items())
now.sort(key=lambda x:x[0])
for i in range(len(now)): now[i] = list(now[i])

result = 0
while len(now) != 0:
    cnt = 0
    for i in range(len(now)): # 연속된 수열 찾기
        if i != len(now) - 1 and now[i][0] + 1 == now[i+1][0]:
            if cnt > 0: cnt += 1
            else: cnt += 2
        else:
            if cnt == 0: # 연속된 수열에 포함되지 않는 수
                result += now[i][0] * now[i][1] # 한 번에 제거
                now[i][1] = 0
            else: # 연속된 수열 찾음
                go = now[i][0]
                now[i][1] -= 1
                idx = i - 1
                for k in range(cnt - 1): now[idx - k][1] -= 1 # 해당 인형들 1개씩 제거
                result += go * cnt
                cnt = 0
    idx = 0
    while idx < len(now): # 다 팔린 특정 크기 인형 제거
        if now[idx][1] == 0:
            del now[idx]
        else:
            idx += 1

print(result)