iamyoungbin

You’ll never forget my name

1 분 소요

Problem

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

Idea

조각의 길이의 합이 구멍의 너비와 딱 맞는 두 개의 레고 조각을 찾는 문제이다. 길이의 합이 구멍의 너비보다 클 경우 더 긴 길이의 조각을 선택해야 하고, 작을 경우 더 작은 길이의 조각을 선택해야 한다.

이 때, 정답이 여러 개일 경우 길이의 차의 절댓값이 가장 두 조각을 출력해야 하는 것을 통해 다음과 같은 아이디어를 떠올렸다.

  1. 우선 가장 크기 차이가 큰 두 조각을 선택한다. 길이가 작은 조각을 L1, 긴 조각을 L2로 둔다.
  2. L1 + L2 가 구멍의 너비보다 작으면 L1 다음으로 작은 조각을 L1으로 선택하고, 구멍의 너비보다 크면 L2 다음으로 큰 조각을 L2로 선택한다.
  3. L1 + L2 = 구멍의 너비의 길이이면 두 조각의 길이를 출력한다. 이 때, 두 조각의 차가 가장 클 때부터 시작해 차가 점점 작아지므로 처음 발견한 두 조각이 차가 가장 큰 조각 쌍이 된다.

다음을 투 포인터 알고리즘을 이용하여 구현했다. 이 때 조각을 찾는 루프문이 left <= right 이 아닌 left < right 동안 반복하게 하였는데 두 포인터가 같은 조각을 중복하여 가리키는 것을 방지하기 위함이다.

테스트케이스 입력을 확인하기 위해 try except문을 이용했다.

Code

import sys

line = sys.stdin.readline

while True:
    try:
        x = int(input()) * 10000000
        n = int(line())
        piece = [int(line()) for _ in range(n)]
        piece.sort()
        
        if n < 2:
            print("danger")
            continue
        
        left, right = 0, n-1
        
        while left < right:
            length = piece[left] + piece[right]
            if length == x:
                print("yes", piece[left], piece[right])
                break
            elif length < x:
                left += 1
            else:
                right -= 1 
        else:
            print("danger")
    except EOFError:
        break

Comment

참고