[Gold V] 러버덕을 사랑하는 모임 - 18233

문제 링크

성능 요약

메모리: 32412 KB, 시간: 48 ms

분류

그리디 알고리즘, 브루트포스 알고리즘

제출 일자

2026년 4월 8일 10:19:11

문제 설명

다영이는 얼마 전에 러버덕을 사랑하는 모임(이하 러사모)에 가입했다. 다영이는 E개의 러버덕 인형을 가지고 있는데, 가입 기념으로 러사모 회원들에게 러버덕 인형을 선물하려고 한다.

러사모 회장에게 의뢰하여 조사해본 결과 러사모 회원은 다영이를 제외하고 N명이 있고, 각 러사모 회원 i는 x_i개 이상 y_i개 이하의 인형만 받는다고 한다. 다영이는 러버덕 인형을 선물 받는 것에 조건을 붙이는 러사모 회원들이 괘씸해서 정확히 P명에게 주는 러버덕 인형들의 합이 E개인 경우에만 인형을 선물하려고 한다. 과연 다영이는 인형을 선물할 수 있을까?

입력

첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000)

그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 x_i와 y_i가 공백으로 구분되어 주어진다. (1 ≤ x_i ≤ y_i ≤ 1,000,000)

출력

다영이가 인형을 선물할 수 있다면 첫 번째 줄에 회원 i에게 선물할 인형 개수를 회원 1부터 N까지 순서대로 공백으로 구분하여 출력한다. 가능한 경우가 여러 개라면 그중 하나를 출력한다.

어떠한 경우로도 인형을 선물할 수 없다면 -1을 출력한다.

---

문제 풀이

문제 분석

이 문제는 다영이가 가지고 있는 총 $E$개의 러버덕 인형을 $N$명의 러사모 회원 중 정확히 $P$명에게 선물하는 방법을 찾는 문제입니다. 인형을 선물받는 각 회원 $i$는 $x_i$개 이상 $y_i$개 이하의 인형을 받아야 한다는 조건이 있습니다. 다영이는 이 조건을 만족하면서 정확히 $P$명에게 총 $E$개의 인형을 선물할 수 있는지 확인하고, 가능하다면 각 회원에게 준 인형의 개수를 출력해야 합니다. 여러 해답이 있다면 그중 하나만 출력하고, 불가능하다면 -1을 출력합니다.

입력은 $N, P, E$와 각 회원별 $x_i, y_i$ 쌍으로 구성됩니다. $N$과 $P$는 최대 20, $E$는 최대 1,000,000, $x_i, y_i$도 최대 1,000,000입니다.

접근 방법

문제에서 $N$의 크기가 20으로 매우 작다는 점이 중요합니다. $N$이 작을 경우, 가능한 모든 경우의 수를 탐색하는 완전 탐색(Brute-Force) 접근 방식이 유효할 수 있습니다.

1. $P$명 선택: $N$명의 회원 중 $P$명을 선택하는 모든 가능한 조합을 고려합니다. itertools.combinations를 사용하면 이를 쉽게 구현할 수 있습니다.
2. 선택된 그룹의 유효성 검사: $P$명의 회원이 선택되면, 이들이 받을 수 있는 인형의 최소 총합($\sum x_i$)과 최대 총합($\sum y_i$)을 계산합니다. 만약 다영이가 가진 인형의 개수 $E$가 이 범위 안에 있지 않다면, 해당 조합으로는 인형을 선물할 수 없습니다 ($E < \sum x_i$ 또는 $E > \sum y_i$).
3. 인형 분배 (그리디): 만약 $E$가 최소 총합과 최대 총합 사이에 있다면 ($\sum x_i \le E \le \sum y_i$), 해당 조합으로는 반드시 인형을 분배할 수 있습니다. 인형을 분배하는 전략은 다음과 같습니다:
   • 먼저 선택된 각 회원에게 최소 요구량인 $x_i$개의 인형을 할당합니다.
   • 이제 $E - \sum x_i$개의 인형이 남았습니다. 이 남은 인형들을 선택된 회원들에게 추가로 분배해야 합니다.
   • 각 회원 $i$는 $y_i - x_i$개만큼의 인형을 추가로 받을 수 있습니다. 남은 인형들을 회원들에게 순서대로 (또는 어떤 순서로든) $y_i - x_i$ 범위 내에서 가능한 한 많이 나누어 줍니다. 이 방법은 그리디하게 동작하며, $\sum x_i \le E \le \sum y_i$ 조건이 만족되면 항상 해를 찾을 수 있습니다.

이 접근 방식은 $N$이 작기 때문에 $N$명 중 $P$명을 선택하는 조합의 수가 감당할 수 있는 수준이므로 효율적으로 문제를 해결할 수 있습니다.

구현 설명

1. 입력 처리 및 회원 정보 저장

• sys.stdin.readline을 사용하여 $N, P, E$를 입력받습니다.
• members라는 리스트를 생성하여 각 회원의 $x_i, y_i$ 값을 [x_i, y_i] 형태의 리스트로 저장합니다.
• idx = [i for i in range(n)]을 통해 회원들의 인덱스 리스트를 만들어 itertools.combinations에 사용할 준비를 합니다.

2. P명 선택 및 유효성 검사

• itertools.combinations(idx, p)를 사용하여 $N$명 중 $P$명을 선택하는 모든 가능한 조합을 반복문으로 탐색합니다. 각 nums 변수에는 선택된 회원들의 인덱스 튜플이 들어 있습니다.
• 각 조합에 대해, 선택된 회원들의 최소 요구 인형의 합 sumx와 최대 허용 인형의 합 sumy를 계산합니다.
• 만약 sumx <= e <= sumy 조건이 만족되면, 이 조합은 유효한 후보입니다. 다음 단계로 넘어가 인형 분배를 시작합니다.

3. 인형 분배 (그리디 방식)

• 유효한 조합이 발견되면, answer 리스트(크기 $N$, 초기값 0)를 생성합니다. 이 리스트는 최종적으로 각 회원에게 주어진 인형의 개수를 저장합니다.
• 선택된 각 회원 i에 대해 answer[i] = members[i][0]으로 최소 요구량 $x_i$를 할당합니다.
• $E - sumx$를 계산하여 남은 인형의 개수 x를 구합니다.
• 다시 선택된 회원 i들을 순회하면서 남은 인형 x를 분배합니다.
  • 회원 i가 추가로 받을 수 있는 인형의 최대 개수는 members[i][1] - members[i][0] (즉, $y_i - x_i$)입니다.
  • add = min(x, members[i][1] - members[i][0])를 통해, 남은 인형 x와 회원이 추가로 받을 수 있는 최대 개수 중 더 작은 값을 add로 결정하고 회원에게 추가로 할당합니다.
  • answer[i] += add로 인형을 추가하고, x -= add로 남은 인형 개수를 갱신합니다.
• 이 과정을 마치면 answer 리스트에는 유효한 인형 분배 결과가 저장됩니다.

4. 결과 출력 및 종료

• print(" ".join(map(str, answer)))를 통해 answer 리스트의 내용을 공백으로 구분하여 출력합니다.
• 문제를 해결하는 하나의 경우만 찾으면 되므로, break 문을 사용하여 combinations 반복문을 즉시 종료합니다.
• 만약 combinations 반복문이 모든 조합을 탐색했지만 break에 도달하지 못했다면 (즉, 어떤 유효한 조합도 찾지 못했다면), for-else 구문의 else 블록이 실행되어 -1을 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • $N$명의 회원 중 $P$명을 선택하는 조합의 수는 $C(N, P)$입니다. $N=20, P=10$일 때 $C(20, 10) = 184,756$이 최대입니다.
  • 각 조합에 대해:
    • sumx, sumy를 계산하는 데 $O(P)$ 시간이 걸립니다.
    • answer 배열 초기화 및 초기 인형 할당에 $O(P)$ 시간이 걸립니다.
    • 남은 인형을 분배하는 데 $O(P)$ 시간이 걸립니다.
  • 따라서 전체 시간 복잡도는 $O(C(N, P) \times P)$입니다.
  • 최악의 경우, $184,756 \times 10 \approx 1.8 \times 10^6$번의 연산이 발생합니다. 이는 일반적인 시간 제한(약 $10^8$ 연산/초) 내에 충분히 수행 가능한 범위입니다.

• 공간 복잡도:

  • members 리스트는 $N$개의 회원의 $x_i, y_i$ 정보를 저장하므로 $O(N)$의 공간을 사용합니다.
  • idx 리스트는 $N$개의 인덱스를 저장하므로 $O(N)$의 공간을 사용합니다.
  • answer 리스트는 $N$개의 정수를 저장하므로 $O(N)$의 공간을 사용합니다.
  • itertools.combinations는 제너레이터이므로 한 번에 하나의 조합만 생성하여 추가적인 큰 공간을 사용하지 않습니다.
  • 따라서 전체 공간 복잡도는 $O(N)$입니다. $N=20$이므로 매우 작은 공간을 사용합니다.

핵심 포인트

1. 작은 N에 대한 완전 탐색 (Brute-Force for Small N): 문제의 제약 조건($N \le 20$)을 이용하여 $P$명을 선택하는 모든 가능한 조합을 시도하는 완전 탐색(itertools.combinations) 접근 방식이 효율적이라는 점입니다. $N$이 크다면 이 방법은 사용할 수 없을 것입니다.
2. 선택된 그룹의 유효성 검사: $P$명의 회원을 선택한 후, 다영이가 가진 인형 $E$개가 선택된 회원들의 최소 요구 인형 총합(sumx)과 최대 허용 인형 총합(sumy) 사이에 있는지(sumx <= E <= sumy) 먼저 확인하여 불가능한 경우를 빠르게 걸러내는 것이 중요합니다. 이 조건이 만족되어야만 해가 존재할 수 있습니다.
3. 그리디한 인형 분배 전략: 유효성 검사를 통과한 그룹에 대해, 우선 각 회원에게 최소 요구 인형($x_i$)을 할당하고, 남은 인형($E - \sum x_i$)을 각 회원이 추가로 받을 수 있는 최대량($y_i - x_i$) 범위 내에서 순서대로 분배하는 그리디 전략이 항상 최적해를 찾을 수 있습니다. $\sum x_i \le E \le \sum y_i$ 조건 덕분에 이 방법은 항상 유효한 분배를 찾아냅니다.

풀이 코드

import sys
from itertools import combinations

input = sys.stdin.readline

n, p, e = map(int, input().split())

idx = [i for i in range(n)]
members = []
for i in range(n):
    members.append(list(map(int, input().split())))

for nums in combinations(idx,p):
    sumx = 0
    sumy = 0

    for i in nums:
        sumx += members[i][0]
        sumy += members[i][1]

    if sumx <= e <= sumy:
        answer = [0] * n

        for i in nums:
            answer[i] = members[i][0]

        x = e - sumx

        for i in nums:
            rest = members[i][1] - members[i][0]
            add = min(x, rest)
            answer[i] += add
            x -= add

        print(" ".join(map(str, answer)))
        break

else:
    print(-1)