[알고리즘][Python] 백준(BOJ) 3649 로봇 프로젝트_파이썬

 

3649 로봇 프로젝트    https://www.acmicpc.net/problem/3649

3649번: 로봇 프로젝트

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 이분 탐색, 정렬

 

 

 

 

 

 

 

 

 

풀이

<내용>

• 1 센티미터 = 10000000 나노미터
• lego의 조각 길이를 정렬한다.
• 구멍은 항상 두 조각으로 막아야 하고 정답이 여러 개인 경우 차이가 가장 큰 것을 출력해야 하므로 lego 리스트의 각각의 끝에서부터 레고 조각을 고른다.
  • lego 한 조각을 두 번 사용할 수 없으므로 왼쪽 인덱스 < 오른쪽 인덱스인 경우에서만 반복한다.
  • lego 두 조각의 합이 구멍의 크기와 같으면 출력하고 break 한다.
  • 구멍의 크기보다 작다면 lego 두 조각의 합을 크게 만들어야 하므로 왼쪽에 있는 인덱스를 오른쪽으로 한 칸 옮긴다.
  • 구멍의 크기보다 크다면 lego 두 조각의 합을 작게 만들어야 하므로 오른쪽에 있는 인덱스를 왼쪽으로 한 칸 옮긴다.

---

• 테스트 케이스가 여러 개이기 때문에 이를 고려해서 처리해야 한다.
  • try, except 구문을 통해 해결한다.

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

while True:
    try:
        x = int(input()) * 10000000
        n = int(input())
        lego = [int(input()) for _ in range(n)]
        lego.sort()
        i, j = 0, n-1
        flag = True
        while i < j:
            if lego[i] + lego[j] == x:
                print('yes %d %d' %(lego[i], lego[j]))
                flag = False
                break

            elif lego[i] + lego[j] < x:
                i += 1
            else:
                j -= 1
        if flag:
            print('danger')
    except:
        break