[BOJ 3649 🥇5] 로봇 프로젝트 (Python)

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|가 가장 큰 것을 출력한다.

 

예제 입력 1 

1
4
9999998
1
2
9999999

 

예제 출력 1 

yes 1 9999999

 

⭕ CODE

# 1센티미터 = 10000000 나노미터

# 테스트 케이스 수가 주어지지 않았으므로
# try 실행하다가 에러가 발생하면 expect 실행
while True:
    try:
        # 구멍의 너비
        x = int(input())

        # 레고 조각의 수
        n = int(input())

        arr = []
        for _ in range(n):
            # 레고 조각의 길이 l 나노미터
            l = int(input())
            arr.append(l)

        # 이분 탐색을 사용하기 위한 정렬
        arr.sort()

        # 시작과 끝점
        s = 0
        e = n-1

        # 두 조각이 있는지 없는지 판별하기 위한 flag
        flag = False

        # 서로 다른 두조각이여하므로
        # s가 e보다 작을때만 탐색 같은경우는 존재할 수 없다
        while s < e:
            # 두 조각의 합이 구멍의 크기와 같다면 정답 출력
            if arr[s] + arr[e] == x * 10000000:
                print('yes',arr[s],arr[e])
                # 가능하므로 flag는 True
                flag = True
                break
            # 합이 구멍의 크기보다 작다면 시작점 +1
            elif arr[s] + arr[e] < x * 10000000:
                s += 1

            # 합이 구멍의 크기보다 크다면 끝점 -1
            else:
                e -= 1

        # 두 조각이 없다면 danger 출력
        if flag == False:
            print('danger')
    except:
        break

✏️ Comment

이분탐색을 사용하여 구멍의 크기와 비교하여 문제를 풀어주었다.

이 문제에서 시간이 오래 걸린 부분은 s와 e는 인덱스로 지정해주었다. 그래서 문제의 조건에 의해서 두 조각을 구하는 것이므로 s와 e는 달라야 하는데 while 조건으로 s <= e로 지정해주어 틀렸었다. 종료 조건을 잘 확인하자