[Gold IV] 극적인 승리 - 33542
성능 요약
메모리: 224856 KB, 시간: 1308 ms
분류
정렬, 이분 탐색
제출 일자
2025년 5월 23일 20:12:05
문제 설명
주원이는 동현이와 “양손으로 공 던져서 과녁 맞추기” 경기를 하고 있다. 경기는 두 명이 번갈아 가면서 차례를 진행하며, 선수는 자신의 차례마다 양 손에 공을 하나씩 들고 각각 과녁을 향해 던진다.
과녁은 총 $N$개 있으며 $1$부터 $N$까지의 정수 번호가 붙어 있다. $i$번 과녁은 왼손으로 맞추면 $L_i$점, 오른손으로 맞추면 $R_i$점을 준다. 단, 과녁 하나에 두 공이 모두 맞으면 무효라서 $0$점이다. 경기가 끝날 때 얻은 점수의 합이 더 높은 사람이 이긴다.
시간이 지나 어느덧 주원이의 마지막 차례만 남았다. 현재 동현이는 $A$점, 주원이는 $B$점을 얻었다. 주원이는 쇼맨십을 중요시하기 때문에, 동현이를 최대한 극적으로 이기고 싶다. 즉, $A$점보다 높으면서 가능한 낮은 점수로 게임을 끝내고 싶다. 주원이는 이 종목의 초고수이기 때문에 왼손/오른손 각각 원하는 과녁을 무조건 맞출 수 있고, 어떤 손은 일부러 맞추지 않을 수도 있다.
주원이가 어떻게 해야 최대한 극적으로 이길 수 있는지를 구하여라. 단, 어떻게 해도 동현이보다 높은 점수를 얻으며 끝내지 못한다면 “No”를 출력한다.
입력
첫 번째 줄에 동현이의 점수 $A$, 주원이의 점수 $B$가 공백으로 구분되어 주어진다.
두 번째 줄에 과녁의 개수 $N$이 주어진다.
세 번째 줄부터 $N$개의 줄에 걸쳐 과녁을 맞췄을 때 얻는 점수가 주어진다. 이 중 $i$번째 줄에는 $i$번 과녁을 왼손, 오른손으로 맞췄을 때 각각 얻는 점수인 $L_i$, $R_i$가 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 주원이가 왼손, 오른손으로 각각 노릴 과녁의 번호를 나타내는 $X$, $Y$를 공백으로 구분하여 출력한다.
두 값 모두 $-1$이거나 $1$ 이상 $N$ 이하의 양의 정수여야 한다. 양의 정수인 경우 맞춰야 할 과녁 번호를 의미하며, $-1$인 경우 맞추지 않는다는 의미이다. $X=Y$인 경우 주원이는 0점을 얻음에 유의하라.
주원이가 어떻게 해도 동현이를 이기지 못한다면, 대신 첫 번째 줄에 “No”를 출력한다.
💡 해결 방법
💻 코드
# https://www.acmicpc.net/problem/33542
#https://upload.acmicpc.net/e1ff45f1-7437-4902-bdc3-f595968ead1a/
from sys import stdin
input = stdin.readline
from bisect import bisect_left
a, b = map(int, input().split())
n = int(input())
left = []
right = []
for i in range(n):
l, r = map(int, input().split())
left.append((l, i + 1))
right.append((r, i + 1))
target = a - b + 1 #이거 이상!
pair = []
if target <= 0:#안맞춰도되면
pair = [-1, -1, -target]
print(pair[0], pair[1])
exit()
for i, v in enumerate(left):
nowpair = [left[i][1], -1 , (left[i][0] + 0) - target]
if nowpair[2] >= 0 and (len(pair) == 0 or nowpair[2] < pair[2]):
pair = nowpair
for i, v in enumerate(right):
nowpair = [-1, right[i][1], (right[i][0] + 0) - target]
if nowpair[2] >= 0 and (len(pair) == 0 or nowpair[2] < pair[2]):
pair = nowpair
#하나 안맞추기, 양손 안맞추기는 끝!
right.sort(key = lambda x : x[0])
for i, v in enumerate(left):
need = (target - left[i][0] , -float('inf'))#이거 이상인거 인덱스를 찾아라!
tidx = bisect_left(right, need)#right는 정렬되어있음 pair[2], 즉, left[i] + right - target 이 최소인(둘의 인덱스가 같은경우 제외) 경우를 구하면된다
while tidx < len(right):#찾은 값이 유효하다면?
if right[tidx][1] == left[i][1]:#과녁 같으면 다음꺼 탐색
tidx = tidx + 1
if tidx == len(right):
break
else:
continue
nowpair = [left[i][1], right[tidx][1], left[i][0] + right[tidx][0] - target]
if len(pair) == 0 or (pair[2] > nowpair[2] and nowpair[2] >= 0):
pair = nowpair
break
if len(pair) == 0:
print('No')
else:
print(pair[0], pair[1])