월요일. 너무 피곤하다.
언제 주말이 올까? 생각하면서 쉬운 문제 하나 풀이해본다.

BOJ 3649 - 로봇 프로젝트 링크
(2022.10.31 기준 G5)
(치팅하면 퇴근 못해)

문제

n개의 레고 중 x 센티미터 너비를 가진 구멍을 정확하게 막을 레고 두 조각 출력

알고리즘

합이 정확하게 x가 되는 두 레고를 찾아야 한다. 두 포인터의 정석.

풀이

먼저 오름차순으로 정렬을 해야 한다.
그리고 두 포인터를 전체 범위의 양 끝으로 잡고 범위를 서서히 좁혀나간다.

만약 두 포인터가 가르키는 레고 길이의 합이 x보다 크다면 길이가 긴 쪽인 오른쪽을 좁히면 된다.
합이 x보다 작다면 길이가 짧은 쪽인 왼쪽을 좁히면 된다.
끝까지 찾지 못한다면 danger를 출력하면 된다.
정말 간단한 두 포인터 문제다.

주의사항

하지만 맞왜틀할 수 있다.
n의 범위는 0 이상 1000000 이하이다.
레고 조각의 개수가 0개나 1개가 들어올 수 있단 말이다. 그러면 무조건 두 조각은 찾지 못하므로 danger를 출력해야 한다.

코드

import sys; input = sys.stdin.readline

while True:
    try: # EOF 처리
        x = int(input()) * 10000000 # 구멍은 cm이므로 nm로 변환
    except:
        break
    n = int(input())
    lego = sorted(int(input()) for _ in range(n)) # 레고 길이를 오름차순으로 정렬

    # 0개나 1개면 두 조각을 찾지 못하므로 danger 출력
    if n < 2:
        print('danger')
        continue

    # 두 포인터
    start = 0; end = n - 1
    length = lego[start] + lego[end] # 합
    while start != end:
        if x < length: # 합이 x보다 크다면 end를 1 감소
            length -= lego[end]
            end -= 1
            length += lego[end]
        elif length < x: # 합이 x보다 작다면 start를 1 증가
            length -= lego[start]
            start += 1
            length += lego[start]
        else: # 합이 x와 같다면 yes 및 두 포인터가 가르키는 레고 길이 출력
            print('yes %d %d' % (lego[start], lego[end]))
            break
    else: # start와 end가 같아지면 danger 출력
        print('danger')

여담

두 포인터의 정석인 문제였다.
이 문제를 풀고 용액 시리즈로 넘어가면 좋을 듯? 하다.