[Python/BOJ] 3649. 로봇 프로젝트

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

3649번: 로봇 프로젝트

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 조각 찾기 함수 정의
def find_piece() :
    # 1-1. left, right 설정
    left, right = 0, n-1
    # 1-2.
    while left < right :
        summation = lego[left] + lego[right]
        # 1-2-1. 해당 인덱스 값이 x보다 작은 경우
        if summation < x : left += 1
        # 1-2-2. 해당 인덱스 값이 x보다 큰 경우
        elif summation > x : right -= 1
        # 1-2-3. 해당 인덱스 값의 합이 x와 같은 경우
        else :
            # 결과 출력 후 리턴
            print(f'yes {lego[left]} {lego[right]}')
            return
    # 1-3. 결과 출력 후 리턴
    print('danger')
    return
# 2.
while True :
    try :
        # 2-1. 구멍의 너비 단위 바꾸기
        x = int(input()) * 10 ** 7
        # 2-2. 레고 조각 정렬하기
        n = int(input())
        lego = [0] * n
        for i in range(n) : lego[i] = int(input())
        lego.sort()
        # 2-3. 조각 찾기 함수 실행
        find_piece()
    except : break