BOJ [G4|27279] 조사전달(python)

문제

만식이네 부대에서는 제설 등의 사역에 차출이 필요한 경우, 조사전달을 진행하여 각 병사가 어떤 사역을 진행할 수 있는지 조사전달 체계에 입력한 뒤, 해당 내용을 통합하여 차출자를 선발한다.

오늘 진행해야 하는 사역은 총
$M$개이다. 하루 동안 진행되는 사역인 만큼 병사는 최대 하나의 사역에만 차출될 수 있으며, 각 사역에는 여러 명의 병사가 필요할 수도 있다. 이에
$N$명의 모든 병사들은
$M$개의 사역에 대한 조사전달을 진행하였고, 각 병사는 적어도 하나의 사역에는 차출이 가능하다고 답했다. 하지만 갑작스럽게 조사전달 체계가 고장 나는 바람에, 각 병사가 가능하다고 답한 사역의 개수만이 체계에 저장되었다.

고장 난 조사전달 체계를 보던 만식이는 체계에 저장된 정보만으로 각 병사들이 어떻게 답변했을지 유추해보고 있었다. 그러던 중, 문득 병사들이 어떻게 답변했더라도 모든 사역에 필요한 인원을 차출하는 방법이 있을지 궁금해졌다. 호기심이 많은 만식이를 위해, 만식이의 궁금증을 해결해 주자!

문제

풀이

0	1	2	3	4
1	2	3	3	4
1	2	1	1

일단 이 문제를 보고, 순서가 필요 없고 크기와 관련이 있는것 같아 정렬을 시켜보았다

0	1	2	3	4
1	2	3	3	4
1	1	1	2

위의 표를 기준으로 생각해보자.
가장 최악의 상황은 무엇일까?
가장 적은 인원이 필요한 작업에 가장 많은 인원이 몰려버리는 것이다.
다시말해 병사들이 쉬운 작업(필요인원이 적은 작업)에만 몰리는 상황이 되어버리면, 인원이 많이 필요한 작업에 참여할 인원이 없어져버린다.

위배열을 A 아래를 B라고 하자.
A[x]가 n만큼의 작업을 참여할 수 있다면, A가 참여하는 작업은 B[0] ... B[n-1]이라고 생각하면 된다.

의사코드로 표현한다면
B[i] = B[i] - sum([A[j] > i for all j)
를 한 후 모든 B[i]가 0이하이면 YES 하나라도 1이상이면 NO라고 볼 수 있는데... 이렇게하면 너무 오래걸릴것 같아 i와 j에 대해 순회하며 체크하는 방식으로 구현했다.

코드

import sys

input = sys.stdin.readline
"""
사역할 수 없는 경우?

1 2 3 4 4
1 1 1 2

1 2 3 3 4
1 1 1 2

1 2 3 3 4 4
1 1 1 2 3 3
"""

def solve():
    N, M = map(int,input().split())
    
    A = [*map(int,input().split())]
    B = [*map(int,input().split())]

    A.sort()
    B.sort()

    # print(A)
    # print(B)

    i = j = 0
    """
    갈수있는 곳 - 현재까지의 작업 개수 >= 0 이면 작업 가능함.
    => 갈수있는 곳 >= 현재까지 작업개수

    i = 작업 인원
    j = 작업
    """
    for j in range(M): # j = 작업 idx
        #print(f"start work {j}, needs {B[j]}")
        while B[j] and i < N: # 인원이 필요하다면
            if A[i] >= j + 1: # 사역 가능 인원
               i += 1
               B[j] -= 1
            else: # 사역 불가능 인원
               i += 1
        #print(B)
        #print(f"{j} work OK, ")
        if B[j]:
           return False
    return True



if solve():
    print("YES")
else:
    print("NO")

첫번째 for에서는 각 작업에 대해서 체크한다.
while문에서는 해당 병사가 작업이 가능하면(위의 가정을 그대로 적용하여 생각한다.) B[j] -= 1을 해 필요한 작업의 수를 줄인다.
작업에 필요한 인원이 모두 할당됐거나 가능한 병사가 없을때까지 반복한다.

마지막 if문은 가능한 병사가 없지만, 인원이 필요한 경우 NO을 출력하도록 False를 반환한다.

모든 작업에 대해 순회를 완료했다면 YES를 출력한다.

후기

어떻게 그리디 다음에 잡은 문제가 그리디일까...