백준 BAEKJOON 31246번 모바일 광고 입찰 [PYTHON/파이썬]

 

 

 

 

 

 

백준 BAEKJOON 31246번 모바일 광고 입찰 [PYTHON/파이썬]

---

<문제 출처> (SILVER Ⅴ)

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

 

 

 

 

 

 

 

<풀이>

MOLOCO가 제시한 입찰 가격 A와 MOLOCO의 입찰가를 제외한 다른 모든 입찰가 중 최고 가격 B가 주어진다.

목표 낙찰 지면 수가 최소 K개 이상이 되도록 하는 것이 문제의 핵심이다.

즉, B에서 A를 뺀 값들을 리스트에 담은 뒤 오름차순으로 정렬하여

K-1번 째 인덱스를 확인하면 된다. (0번째 인덱스부터 시작하니 -1)

K-1번 째 인덱스의 값이 음수면 최소 K개의 지면을 낙찰 받았다는 것을 의미하여 0을 출력,

양수면 그 값만큼 올려주면 조건을 성립하기 때문에 최소 정수 X라는 것을 의미한다.

 

 

 

 

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
X = []

for _ in range(N):
    A, B = map(int, input().split())
    X.append(B - A)

X.sort()  # 오름차순 정렬

if X[K - 1] < 0:
    print(0)
else:
    print(X[K - 1])