[실버 2] 백준 2790 - F7 (파이썬)

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

풀이

N명의 학생이 있고 각 학생은 자신이 좋아하는 친구 수 B[i]를 갖고 있을 때, 가능한 한 많은 학생이 자신의 친구 수 조건을 만족하도록 친구를 맺도록 하는 것이다.

i번 학생은 정확히 B[i]명의 친구를 갖고 싶어한다

결국 이 문제는 B[i]명을 만족시키는 친구 매칭이 가능한 최대 학생 수를 구하는 것이다.

이를 해결하기 위해, 학생들을 좋아하는 친구 수 기준으로 정렬하고, 뒤에서부터 만족시킬 수 있는지 확인한다.

N = int(input())
B = [int(input()) for _ in range(N)]
B.sort()

학생수와 각 학생이 원하는 친구 수 B[i]를 리스트에 저장한 뒤 오름차순 정렬한다.

answer = 0
max_val = 0
for i in range(N - 1, -1, -1) :
    if B[i] + N >= max_val :
        answer += 1
    else :
        break

    max_val = max(max_val, B[i] + N - i)

i를 N - 1부터 0까지 역순으로 순회한다.

• B[i] + N - i의 의미는?
  • 이 학생이 원하는 친구 수 B[i]를 만족하려면, 자기보다 친구를 더 적게 원하는 학생들 중 몇 명을 친구로 삼아야 함
  • N - i는 이 학생보다 작거나 같은 인덱스의 학생 수.
  • 그래서 B[i] + N - i는 이 학생이 요구하는 친구 수를 맞추기 위해 필요한 최소 범위.
• max_val은 지금까지 본 학생 중 가장 높은 요구 범위이다.
• 만약 현재 학생의 B[i] + N이 max_val보다 작으면, 더 이상 뒤에 있는 학생들은 이 조건을 만족할 수 없음 → break.
• 만족 가능한 학생 수만큼 answer += 1.

코드

# 백준 2790 - F7
# 분류 : 그리디

import sys
input = sys.stdin.readline

N = int(input())
B = [int(input()) for _ in range(N)]
B.sort()

answer = 0
max_val = 0
for i in range(N - 1, -1, -1) :
    if B[i] + N >= max_val :
        answer += 1
    else :
        break

    max_val = max(max_val, B[i] + N - i)

print(answer)