[PS] BOJ 25631 / 마트료시카 합치기

Minjun Kim

14 May 2025 • 1 min read

문제 링크: https://www.acmicpc.net/problem/25631

Thumbnail: Photo by Didssph (Unsplash)

마트료시카 인형 쌓기~

풀이

크기가 서로 다른 마트료시카 인형들은 결과적으로 가장 큰 크기의 1개 인형으로 합쳐질 수 있다. 합쳐지지 못하고 인형이 하나 더 남게 되는 경우는 결국 같은 크기의 인형이 중복될 경우이므로, 인형을 크기를 기준으로 개수를 세어 가장 많이 중복된 개수가 모든 마트료시카 인형을 합치고 남은 인형의 개수가 된다.

전체 코드

input = open(0).readline

N = int(input())

# 입력으로 주어진 모든 마트료시카를 크기를 기준으로 세어, 가장 많이 중복된 길이의 개수가 결과적으로 합치고 남는 마트료시카와 같다.
counter = {}
res = 0
for a in map(int, input().split()):
    if a in counter:
        counter[a] += 1
    else:
        counter[a] = 1
    res = max(res, counter[a])

print(res)

solution.py