[Python] 백준 32374 - 선물 고르기

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

 

들어가기에 앞서...

이제는 대학생이 되었다.

고등학교때 디코에서만 보던 멋진 분들을 어느새 내 카톡 친구창에서 보게되었다.

이제 진짜 열심히 할 때가 되었다.

풀이

문제를 잘 읽어보면 선물 상자에 모든 선물을 담을 수 없는 경우는 입력으로 주어지지 않는다고 하였다.

그말인즉슨 선물 상자에 반드시 모든 선물을 다 담을 수 있다.

 

그러니까 선물들과 선물상자를 크기순으로 쭉 정렬해보면

$a_i$ 선물은 반드시 $b_i$ 안에 들어갈 수 있다.

 

문제에서 주어진 예제를 예시로 들면 아래 그림과 같다.

 

선물의 크기가 상자의 크기 이하여서 상자에 들어갈 수 있는 경우를 파란색 화살표로 표현하였다.

 

만약 파란색 화살표가 아래 그림과 같이 오른쪽으로 기울어져있다면 어떻게 될까?

당연히, 선물이 자연스럽게 상자 안에 들어갈 수 있다.

 

그런데 만약 화살표가 왼쪽으로 기울어져있다면 어떻게 될까?

 

선물의 크기와 상자의 크기에 따라 들어가는 것도 있고, 못들어가는 것도 있다. 이거는 좀 따져봐야한다.

 

 

여기서, 지금 13, 9, 13 상자는 다른 사람이 이미 가져간 상태이다.

따라서 우리는 문제의 조건에 따라 9 상자를 가져가야하는데, 과연 9 상자에 들어갈 수 있는 최대 크기의 선물을 어떻게 구할 수 있을까?

 

 

일단 7짜리 선물은 가져갈 수 있겠다.

혹시 7보다 더 큰 선물은 못가져갈까? 9는 가져갈 수 있을 것 같은데(왼쪽으로 기울어진 화살표 가능)

 

 

그러면 자연스럽게 7짜리 선물은 9짜리 상자에 넣으면 될 것이다.

 

사실 이런 논리로 그냥 9짜리 상자에 들어갈 수 있는 선물 중 가장 큰 것을 고르면 나머지는 그냥 알아서 잘 배치될 것이다.

이는 O(N)에 쉽게 구할 수 있다.

 

N, K = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
crr = list(map(int, input().split()))
cnt = {}
for i in brr:
    cnt[i] = cnt.get(i, 0) + 1
for i in crr:
    cnt[i] -= 1
tmp = 0
for i in cnt:
    if cnt[i] and i > tmp:
        tmp = i
ans = 0
for i in arr:
    if i <= tmp and i > ans:
        ans = i
print(ans)