[백준/26149] 선물의 재분배 (Python)

Problem : https://www.acmicpc.net/problem/26149

26149번: 선물의 재분배

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:38:17

 

---

 

문제 설명

 

 

성현이는 N명의 알고리즘 동아리 부원들에게 총 M개의 선물을 주기로 했다.

하지만, 부원들에게 선물을 그냥 주는 건 재미없다고 생각한 성현이는 아래와 같은 방식으로 선물을 나눠주기로 했다.

우선, N명의 부원들에게 1부터 N까지의 번호를 매긴 뒤, 부원들에게 각각 A_1, A_2, ..., A_N개의 선물을 나눠준다. 그리고, 각 부원이 받아야 하는 선물의 개수 B_1, B_2, ..., B_N 을 알려준다.

이후, N명의 부원들은 아래의 연산만을 적절히 사용해서 본인이 받아야 하는 선물의 개수를 맞춰나가야 한다. 단, 시간이 너무 오래 걸리면 안 되기 때문에, 두 연산을 합해서 총 2N번 이하로 사용해야 한다.

 
+ i x : i 번 부원을 제외하고, 현재 선물을 가장 많이 가지고 있는 부원을 j 라고 하자. 이때, j 번 부원이 i 번 부원에게 선물 x 개를 준다.
 - i x : i 번 부원을 제외하고, 현재 선물을 가장 적게 가지고 있는 부원을 j 라고 하자. 이때, i 번 부원이 j 번 부원에게 선물 x 개를 준다.
두 경우 모두, 조건을 만족하는 j가 여럿 있다면 그중 번호가 가장 작은 부원이 선택된다.
성현이는 위와 같은 서프라이즈를 준비한 뒤, 검증을 위해 프로그램을 짜서 미리 가능한 결과 중 하나를 만들어보기로 했다.

 

 

입력 및 출력

 

입력

 

첫째 줄에는 알고리즘 동아리의 부원 수 N과 총 선물의 수 M이 주어진다. (1 <= N <= 200000, 1 <= M <= 10^9
둘째 줄에는 각 부원들에게 나눠준 선물의 개수 A_1, A_2, ..., A_N이 주어진다. (0 <= Ai, sum(Ai) = M)
셋째 줄에는 각 부원들이 받아야 하는 선물의 개수 B_1, B_2, ..., B_N이 주어진다. (0 <= Bi, sum(Bi) = M)
조건을 만족하는 모든 입력에 대해 답이 존재함이 보장된다

 

출력

 

첫째 줄에 사용한 연산의 수 K를 출력한다. ( K <= 2N ) 
그 뒤, K개의 줄에 걸쳐 사용한 연산을 순서대로 출력한다.
모든 연산은 실행 가능해야 한다. 즉, 존재하지 않는 부원을 가리키는 연산이나, 주는 입장의 부원이 가지고 있는 선물보다 더 많은 선물을 요구할 수 없다. 또한, 1 <= x 를 만족해야 한다.

 

입력 예시

 

4 20
2 4 6 8
3 7 4 6

 

출력 예시

 

5
+ 1 1
+ 2 4
+ 3 1
- 3 3
- 1 3

 

 

---

 

풀이

 

다음 두 과정으로 나눌 수 있다.

 

• 받아야 할 선물의 개수가 가장 큰 부원에게 모든 선물 모으기
  • 이 부원의 인덱스를 maxidx라고 하면, 그리고 이 부원을 제외한 부원들 중 지금 가지고 있는 선물이 가장 큰 경우를 val이라고 두자.
  • 명령어는 + maxidx val이 될 것이다.
  • 이 과정은 (N-1) 이하임이 보장된다.
• 다른 모든 사람이 앞서 모은 부원에게 선물 가져오기
  • 어떤 부원의 인덱스를 i, 이 부원이 가지고 있어야 할 선물을  target이라고 두자.
  • 명령어는 + i target이 될 것이다.
  • maxidx가 가진 선물 target개를 i에게 주게 된다.
    • 이 때 maxidx가 보유한 선물 >= maxidx가 가지고 있어야 할 선물 == max(전체 가지고 있어야 할 선물) 을 만족하므로, 항상 maxidx가 가장 많은 선물을 가지고 있음이 보장된다.
  • 이 작업 역시 (N-1) 이하임이 보장된다.
  • - i x 연산은 가지고 있어야 할 선물이 0인 부원들을 고려할 수 없다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

orig = list(map(int, input().split()))
target = list(map(int, input().split()))

log = []
orig_order = sorted([(-x, i) for i, x in enumerate(orig)])
maxidx = target.index(max(target))

for i in range(N) :
  if not orig_order[i][0] :
    break
  if orig_order[i][1] == maxidx :
    continue
  log.append('+ {} {}'.format(maxidx+1, -orig_order[i][0]))

for i in range(N) :
  if i == maxidx or not target[i] :
    continue
  log.append('+ {} {}'.format(i+1, target[i]))

print(len(log))
print(*log, sep='\n')

풀이 완료!