[Python] 백준 31650번 Maximizing Productivity

문제

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

입력

• The first line consists of N and Q.
• The second line consists of  c_1, c_2, c_3, ..., c_N (1 ≤ c_i ≤ 10^6).
• The third line consists of t_1, t_2, t_3, ..., t_N (1 ≤ t_i ≤ 10^6).
• The next Q lines each consist of two integers V (1 ≤ V ≤ N) and S (1 ≤ S ≤ 10^6).

출력

• For each of the Q queries, output YES or NO on a new line.

입력 예제

5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1

출력 예제

YES
NO
YES
YES
NO

문제 해석

Bessie는 Farmer John이 운영하는 농장을 방문할 수 있는지 판단하는 문제

=================================== 입력 =================================== 
첫번째 줄 입력으로 들어오는 N과 Q -> 농장의 수, Bessie가 방문을 시도할 횟수
두번째 줄은 각 농장이 닫히는 시간
셋째 줄은 Bessie가 이동하는데 걸리는 시간
이후부터는 Q번 V와 S를 입력받으며 Bessie가 방문을 시도한다.
V는 YES를 출력하기 위해 Bessie가 방문해야하는 최소 농장의 개수
S는 Bessie가 일어나는 시간 -> Bessie가 이동하는 시간 + S = 방문하는데 걸리는 시간

=================================== 출력 =================================== 
농장이 닫는시간과 Bessie가 이동하는 시간과 일어나는 시간, 최소 방문해야하는 농장(V)
이 주어질 때 조건을 만족할 Bessie가 최소 V개의 농장을 방문할 수 있다면 YES 없다면 NO
를 출력한다.

문제 풀이

• for 문을 돌려 Bessie가 일어나는 시간과 이동하는 시간을 더해 일일히 계산하면 시간초과가 발생한다.
• 따라서 시간 복잡도를 줄이기 위해 필요한 연산을 최소화 해야한다.
• 먼저 농장이 닫는 시간과 Bessie가 걸리는 시간을 farms와 time배열에 입력받은 후 두 배열의 차이를 diff 배열에 저장한다. -> 이렇게 하면 diff배열에는 farm[i] - time[i]가 저장되는데 이는 Bessie가 일어나도 되는 최대 시간이다.
• 일어날 수 있는 시간을 모두 구했다면 v개의 농장을 방문할 수 있는지 확인하기 위해 내림차순으로 정렬한다.
• 이후, 정렬된 diff배열의 V - 1번째 인덱스가 일어나도 되는 시간보다 크다면 V개의 농장 방문에 성공한 것이므로 YES 그렇지 않다면 실패한 것이므로 NO를 출력한다. 

코드

n, q = map(int,input().split())
farms = list(map(int,input().split()))
time = list(map(int,input().split()))

diff = [0] * n
# Bessie가 일어날 수 있는 시간 구하기
for i in range(n):
    diff[i] = farms[i] - time[i]
diff.sort(reverse=True)

for i in range(q):
    # 방문가능한 농장 수, 일어나는 시간
    v, s = map(int,input().split())
    if diff[v - 1] > s:
        print('YES')
    else:
        print('NO')