[Python] 백준 30645 - 인형 전시

https://www.acmicpc.net/problem/30645

문제

탁자 위에 인형을 전시하려고 한다. 탁자는 위에서 보았을 때 R개의 행과 C개의 열을 가진 R × C개의 칸을 가진 2차원 배열이며, 각 칸에 하나의 인형을 전시할 수 있다. 현재 전시할 수 있는 인형은 N개이며, 탁자 위에 N개의 인형을 모두 전시할 필요는 없다.

탁자를 정면으로 보면 1행에 놓은 인형들이 맨 앞쪽에 있는 방향으로 보게 되는데, 같은 열에 있는 인형들에 대해 앞쪽 행에 인형을 놓은 경우 앞쪽 인형보다 뒤쪽 행에 있고 높이가 앞쪽 인형의 높이 이하인 인형은 앞쪽 인형에 가려져 보이지 않게 된다.

이때, 탁자에 인형들을 적당히 배치했을 때 탁자의 정면 방향에서 보이는 인형의 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 탁자의 행의 개수 R과 열의 개수 C가 주어진다.

두 번째 줄에 탁자에 전시할 수 있는 인형의 개수 N이 주어진다.

세 번째 줄에 N개의 인형의 높이 h1, h2, …, hN이 주어진다.

출력

탁자의 정면 방향에서 보이는 인형의 개수의 최댓값을 출력한다.

 

---

풀이

전형적인 정렬 + 그리디 문제이다.

키 큰 인형 순서대로 정렬한 다음 하나하나씩 판에 놓은 다음 카운팅 하는 문제이다.

 

그런데 구현하기가 귀찮다.

 

머리가 좋으면 몸이 고생을 안한다는 말이 있으니까,

나는 정렬을 빼버리고 O(n) 안에 풀어볼 것이다.

 

일단 문제에서 구하는 값은 볼 수 있는 인형의 최댓값이다.

바보가 아닌 이상 키 큰 순서로 판에 올려놓겠지....

당연히 그럴 것이라고 상황을 가정한다.

 

키가 작은 인형들이 앞에 놓인다면, 잘만 놓는다면 모든 인형들이 보일 수도 있을 것이다.

 

여기서 문제가 되는 것은 바로 똑같은 인형이 여러 개 있을 때는 과연 어떻게 되는가? 이다.

 

다음 예제를 보자.

 

문제에서 주어진 예시 입력 1

여기서는 C = 3인데 4짜리 인형이 4개가 있다.

생각을 잘 해보면 4짜리 인형이 4개가 있든 100개 있든 보이는 인형의 개수는 최대 C개 일 것이다.

물론 똑같은 인형이 n개 (n<C)개 있다면 n개가 보일 것이다.

 

이 아이디어를 이용해보자.

 

일단 딕셔너리(또는 리스트도 괜찮다)를 하나 정의하고 리스트를 돌면서 각 원소의 개수를 카운팅해준다(정렬이 필요 없다!)

그 다음에, 딕셔너리의 원소를 돌면서 min(카운팅한 값, C)를 더해나가면 될 것이다!!!

 

 

마지막으로 고려해야 할 함정은, 최종적으로 더한 값이 R*C(판에 있는 칸의 개수)보다 클때는, 그냥 R*C를 출력하는 것이다.

 

이 모든 것을 종합하면 짧은 코드를 짤 수 있다.

 

from collections import defaultdict
R, C = map(int, input().split())
N = int(input())
H = list(map(int, input().split()))
D = defaultdict(int)
for i in H:
    D[i] += 1
ans = 0
for i in D:
    ans += min(D[i], C)
print(min(ans, R*C))