Algorithm

백준 17947번: 상남자 곽철용 (python)

by VICENTE97P4

Dec. 23, 2021, 3:45 p.m.

문제 링크: 17947번: 상남자 곽철용 (acmicpc.net)

이 문제는 잘 알려져있지 않은 문제입니다.

그래서 문제가 안 좋은가? 싶지만 생각보다 괜찮습니다.

하지만 구글에 풀이를 찾아보면 하나도 없습니다..

그래서 제가 포스팅해볼까 합니다.

일단 1~4N까지의 카드 중 버려야 할 카드가 주어집니다.

카드를 버릴 때 시간복잡도에 주의해야 합니다.

그냥 리스트에서 pop해버리면 TLE가 날겁니다.

set을 이용해서 O(1)만에 카드를 버려주도록 합시다.

그리고 점수는 K로 나눈 나머지의 차입니다.

모든 수를 K로 나눈 나머지로 리스트를 만들고 정렬해줍시다.

여기까지는 어렵지 않게 떠올릴 수 있습니다.

문제는 이제부터인데, 철용이보다 점수가 많은 사람이 최대 몇 명인지 구해야 합니다.

그런데 어떻게 매칭을 시켜줘야 할까요?

음.. 일단 언듯 생각해보면 철용이보다 점수가 많은 사람이 최대가 되려면,

철용이보다 점수가 큰 최소값들이 되도록 매칭시키는게 유리할 것 같습니다.

철용이보다 점수가 많기만 하면 되니까 철용이보다 1점이 높든 100점이 높든 아무 상관이 없습니다.

즉, 최대한 차이가 적지만 철용이 점수보다는 큰 두 수를 계속 골라주면 될 것 같습니다.

그런데 input이 최대 40만이라.. N^2은 안 될 것 같습니다. 따라서 모든 경우의 수를 따져보긴 힘듭니다.

최대 NlogN만에 매칭을 끝내줘야 하는데.. 이때 떠올릴 수 있는 기술이 투 포인터 입니다.

매칭된 두 카드의 차가 철용이 점수보다 작으면, 두 번째 포인터를 전진, 크면 포인터 두 개 다를 모두 전진시키면 되겠죠.

그렇게 인덱스 0과 1부터(위 예제에서는 1과 3에 해당하죠.) 투 포인터를 진행하도록 풀면 '틀렸습니다.'가 뜰껍니다.

이런 식으로 투 포인터를 진행하면 해결할 수 없는 반례가 있습니다.

예를 들어 1,3,5,7,9,9가 있다고 하고, 철용이는 1점이라고 합시다.

인덱스를 0과 1부터 시작하는 노멀한 투 포인터로 구하면 정답은 2가 됩니다.

1-3, 5-7이 매칭되고, 9-9는 0이라 철용이와 같은 점수라 제외되기 때문입니다.

하지만 정답은 3입니다. 1-9, 3-7, 5-9로 매칭할 수 있기 때문이죠.

그럼 어떻게 해야 하냐.. 기본적인 부분을 생각해내면 됩니다.

카드 수야 어찌됐건 정답은 최대 M-1명입니다. 이는 남은 카드 수의 절반이죠.

즉, 두 번째 포인터의 시작을 최대 배열 길이의 절반으로 세팅해주면 됩니다.

어? 그러면 최대한 많이 매칭을 못해줄 수도 있지 않나요? 하고 생각할 수 있습니다. 저도 그랬으니까요..

그런데 가만히 생각해보면 아닙니다.

어차피 정답은 많아봤자 남은 카드 수의 절반(정확히는 M-1이죠.)입니다.

그리고 절반보다 앞에 있는 인덱스 카드끼리 매칭시키는 경우는 생각 안해도 됩니다.

물론 그렇게 매칭시킬 수도 있겠습니다마는, 절반보다 앞쪽에 있는 카드끼리 매칭할 수 있다면 당연히

절반보다 뒤쪽에 있는 카드와도 매칭이 가능합니다.

이렇게 1-5를 매칭할 수 있다면

1-7도 매칭할 수 있죠.

카드들은 정렬되어 있으니 뒤로 갈수록 차이는 커지기 때문입니다.

즉, 절반보다 앞쪽에 있는 카드들만 매칭이 가능한 경우는 없습니다.

무조건 절반보다 뒤쪽에 있는 카드와도 매칭시킬 수 있고, 정답을 구할 수 있습니다.

또한, 절반 앞쪽 포인터와 절반 뒤쪽 포인터를 매칭시켰을 때 철용이 점수 이하가 나와서

뒤쪽 포인터를 전진시킬 때 커버 못하는 경우는 걱정하지 않으셔도 됩니다.

어차피 절반 뒤쪽 포인터랑 앞쪽 포인터랑 매칭했을 때 점수가 철용이 점수 이하로 나오면

절반 앞쪽 포인터끼리는 매칭시켜봤자 철용이 점수 이하로 나옵니다.

만일 철용이 점수가 6점이어서

이 경우에서 두 번째 포인터가 전진하여,

9를 카리킨다고 했을 때, 1-3, 1-5, 3-5 매칭은 생각하지 않아도 됩니다.

정렬되어 있으니 둘 사이의 거리가 작을 수록 차이가 작아지기 때문에 당연한 일이죠.

그러니 한 포인터는 0부터, 나머지 한 포인터는 리스트 길이 /2부터 시작하면 됩니다.

코드입니다.

import sys;
input = sys.stdin.readline
N, M, K = map(int, input().split())
card = set(range(1, 4 * N + 1))
for _ in range(M):
a, b = map(int, input().split())
card.discard(a)
card.discard(b)


chul = list(map(int, input().split()))
card.discard(chul[0])
card.discard(chul[1])
chul_score = abs(chul[0] % K - chul[1] % K)
card = list(card)
for i in range(len(card)):
    card[i] %= K
card.sort()
l, r, ans = 0, len(card) // 2, 0

while r < len(card) and ans < M - 1:
    if card[r] - card[l] > chul_score:
        ans, r, l = ans + 1, r + 1, l + 1
    else:
        r += 1

print(ans)

정답은 커봤자 남은 카드 개수의 절반(정확히는 M-1)이다.

이 사실에 집중하면 떠올려낼 수 있는 문제였습니다.

하긴.. 그렇다고는 해도 생각해내기 어려운건 매 한가지죠..

알고리즘 문제풀이 잘하는 사람들 존경스럽습니다.

이런거 쉽게 푸는 사람들이 있던데, 타고난 지능이 높다는 느낌이 듭니다. 부럽군요..

면접준비를 해야 하는데.. CS를 포스팅 해야 하는데..

알고리즘 문제풀이가 더 재밌네요..

백준 greedy two pointer 28 view 1033

fnfOzvSR Feb. 22, 2025, 5:29 p.m.

��%2527%2522\'\"

Updated: Feb. 22, 2025, 5:29 p.m.

fnfOzvSR Feb. 22, 2025, 5:29 p.m.

@@NlRY9

Updated: Feb. 22, 2025, 5:29 p.m.