[알고리즘 문제 풀이][그리디] 백준 3211번 - kino
백준 3211 kino 문제의 풀이 방법을 정리한 내용입니다.
- 문제 설명: https://www.acmicpc.net/problem/3211
3211번: kino
In the first row there is an integer N, 2 ≤ N ≤ 10 000, number of friends. In the next N rows there is one integer per row Zi, 1 ≤ Zi < N. That numbers represent requests of all Mirko’s friends, that is, minimal number of people they are willing to
www.acmicpc.net
미르코 (Mirko) 는 친구들을 영화관에 데려가려고 합니다. 각 친구들은 여럿이서 가는 것을 좋아하기 때문에 일정 수의 다른 친구들이 같이 가달라고 요청합니다. 하지만 모두 초대할 돈이 부족하여 최소한의 인원만 초대하고자 합니다. 친구들의 요구를 충족하면서 1명 이상의 최소 인원을 결정하세요.
요약해서 보더라도 복잡해보이지만 첫번째 예제를 보면 이해가 더 쉬울 것 같습니다.
2명의 친구가 원하는 값이 1 1 로 주어졌다면 각 사람은 나 외에 1명이 더 따라와야한다는 것을 의미합니다.
그래서 2명 중 1명만 데려갈 수는 없고 2명을 다 데려가야합니다.
만약 세번째 예제와 같이 3 4 3 3 3 이 주어졌다면 총 5 명의 친구들이 나 외에 3명이 더 있어야해, 나 외에 4명이 더 있어야해, ... 와 같이 요청한 것이 됩니다.
- 문제 풀이:
돈이 없어서 최소한의 친구들을 영화관에 데려가는 것이 목표이기 때문에 당연히 최소한의 다른 친구들만 데려가도 된다고 말한 사람들부터 후보로 넣으면 될 것입니다. (나는 최소 5명은 가야 따라갈 거야... 하는 사람은 5명을 이미 구해줘야하지만 극단적으로 난 나 말고 아무도 필요 없어라고 말하면 그 사람만 데려가면 됩니다.)
그래서 각자 원하는 동반 친구수대로 정렬을 해줍니다.
예제 3의 입력을 기준으로 한다면 3 4 3 3 3 을 가지고 정렬을 하면, 3 3 3 3 4 가 될 것입니다.
그러면 앞에서부터 최소한으로만 요청하는 친구들이므로 포함을 시켜줍니다.
3 3 3 3 4 [ 총 1명 포함 ]
맨 처음 3을 요청한 친구는 일단 포함은 되었지만 나 외에 3명이 더 있어야한다는 요구는 아직 충족하지 못했습니다.
그 다음 3을 요청한 친구를 넣어도 역시 나 외에 3명이 더 있어야한다는 요구를 아직 충족하지 못했습니다.
3 3 3 3 4 [ 총 2명 포함 ]
그 다음 3을 넣어도 마찬가지입니다. 총 3명이 추가되었기 때문에 아직까지 본인 외에는 2명의 친구만 데려가고 있습니다.
3 3 3 3 4 [ 총 3명 포함 ]
그러다가 다음 3을 요청한 친구를 포함하면, 이제 총 4명이 되었으므로 모두가 나 외에 3명이 필요하다고 요청한 요구가 충족됩니다.
3 3 3 3 4 [ 총 4명 포함 ]
그래서 최소 인원수는 4명이 됩니다.
여기까지 보면 이런 생각이 들 수도 있습니다. 그러면 맨 처음 요청부터 계속 다시 보면서 지금 총 포함한 인원수가 앞선 친구들이 원하는 조건을 만족하는지 여부를 다 확인해봐야하나? 하는 의문입니다.
하지만 이미 정렬을 해두었기 때문에 마지막 친구의 요구가 만족된다면 그 앞은 작거나 같은 값이므로 자연스럽게 다 만족되게 됩니다. (그리디)
예를 들어서 마지막으로 포함된 친구의 요청이 나 외에 5명을 데려가야해였고, 이 친구를 포함하여 총 6명이 되어 요구를 만족했다고 가정해보겠습니다. 그러면 정렬된 상태이므로 그 앞의 요청들은 예를 들면, 3명, 4명,... 많아봐야 5명을 요청했을 것입니다. 그러면 당연히 현재 6명의 인원이므로 요구가 충족이 될 수 밖에 없습니다.
이를 토대로 코드를 작성하면 아래와 같습니다.
for 문을 진행하면서 (= for 문의 숫자를 이용하여 현재까지 포함된 인원수와 같이 생각하면 됩니다),
현재까지 포함된 인원이 마지막 친구가 요청한 값을 만족한다면 거기서 break 를 하면 됩니다.
- 코드 (Python):
n=int(input())
arr=[]
for i in range(n):
arr.append(int(input()))
arr.sort()
for i in range(n):
if arr[i] < i+1:
print(i+1)
break
- 실수 포인트 & 반례:
문제의 예제 외에 필요한 반례는 없었습니다.