문제 링크: https://www.acmicpc.net/problem/26091

Thumbnail: Photo by Stephen Kidd (Unsplash)

문제 이름에 걸맞는 현대차로 썸네일 들고 왔습니다 😄

풀이

구상

가장 많은 팀을 소프트웨어 아카데미에 참여시키기 위해서는 결국 점수가 가장 높은 사람과 가장 낮은 사람을 같은 팀에 붙이는 식으로, 팀의 능력치가 중간 값에 맞춰지도록 하는 방식을 구상했다.

그에 따라, 먼저 학회원들의 성적을 입력 받은 뒤 오름차순으로 정렬한다. 배열의 양 끝에서 원소를 각각 취해 팀을 구성하면 된다.

구현

stats = sorted(map(int, input().strip().split()))

max_teams = N // 2
teams = 0
for i in range(max_teams):
    total = stats[i] + stats[N - i - 1]
    if total >= M:
        teams += 1

고민

​일단 맞추긴 했으나, 분명 이 코드는 다음과 같은 반례가 존재한다.

예제 입력

6 10
1 1 2 2 3 7

예상 출력

1

실제 잘못된 출력

0

이는 위 코드가 단순히 전체 수열의 평균을 찾아서 일어나는 현상인데, 위와 같이 대부분의 학회원들의 능력치가 낮고 극히 일부만 높은 경우는 중간 값으로 찾게 되면 팀의 능력치가 \(M\)을 넘지 못하는 경우가 생길 수 있다. 따라서, 위와 같은 반례도 통과할 수 있는 풀이를 찾아보자.

투 포인터

결국은 투 포인터다! 정렬된 배열에서 2개의 포인터로 부분 수열을 찾아내는 기법인데, 이번 문제도 길이 2의 부분 수열을 탐색하는 문제이므로 적용할 수 있다.

input = open(0).readline
N, M = map(int, input().strip().split())
stats = sorted(map(int, input().strip().split()))

def solution():
    teams = 0
    prev_min = 0
    for i in range(N-1, -1, -1):  # 능력치가 높은 쪽에서부터 반복하면서
        j = prev_min    # 높은 쪽 능력치는 작아지므로, 낮은 쪽 능력치는 이전 능력치보다 높은 사람 중에서 골라야 한다.
        while stats[i] + stats[j] < M:
            j += 1
            if j >= N:
                break
        if j >= i:  # 탐색이 종료되는 경우: 오른쪽 포인터(작은쪽 능력치)가 왼쪽(i, 큰쪽 능력치)과 같아지거나 커질 때
            return teams

        if stats[i] + stats[j] >= M:
            teams += 1
        prev_min = j + 1
    return teams

print(solution())

전체 코드

배열의 양 끝을 탐색하는 방식 (반례가 존재함)

input = open(0).readline
N, M = map(int, input().strip().split())
stats = sorted(map(int, input().strip().split()))

max_teams = N // 2
teams = 0
for i in range(max_teams):
    total = stats[i] + stats[N - i - 1]
    if total >= M:
        teams += 1

print(teams)

투 포인터 (위 반례도 풀 수 있는 코드)

input = open(0).readline
N, M = map(int, input().strip().split())
stats = sorted(map(int, input().strip().split()))

def solution():
    teams = 0
    prev_min = 0
    for i in range(N-1, -1, -1):  # 능력치가 높은 쪽에서부터 반복하면서
        j = prev_min    # 높은 쪽 능력치는 작아지므로, 낮은 쪽 능력치는 이전 능력치보다 높은 사람 중에서 골라야 한다.
        while stats[i] + stats[j] < M:
            j += 1
            if j >= N:
                break
        if j >= i:  # 탐색이 종료되는 경우: 오른쪽 포인터(작은쪽 능력치)가 왼쪽(i, 큰쪽 능력치)과 같아지거나 커질 때
            return teams

        if stats[i] + stats[j] >= M:
            teams += 1
        prev_min = j + 1
    return teams

print(solution())