백준 3649 : 로봇 프로젝트 (Python)

본문 링크

import sys
input=sys.stdin.readline


while True:
    try:
        x=int(input())
        T=int(input())
        L=[]

        for i in range(T):
            L.append(int(input()))
        L.sort()

        start=0 ; end=T-1 ; answer=-1 ; answer_list=[]

        while start<end:
            if L[start]+L[end]==x*10000000:

                if answer<abs(L[end]-L[start]):
                    answer_list=[L[start] , L[end]]
                    answer=abs(L[end]-L[start])
                start+=1

            elif L[start]+L[end]>x*10000000:
                end-=1
            else:
                start+=1

        if len(answer_list)!=0:
            print("yes %d %d"%(answer_list[0] , answer_list[1]))
        else:
            print('danger')
    except:
        break

📌 어떻게 접근할 것인가?

문제 자체는 되게 쉽지만 n의 범위는 0 ≤ n ≤ 1000000 이다.
완전탐색으로 풀기에는 매우 오래 걸리기 때문에 투 포인터를 사용하였다.

📌 어떻게 투 포인터를 사용할 것인가?

먼저 리스트 L을 정렬해준후 , start=0 ; end=T-1로 잡은후
L[start]+L[end]값이 x보다 크면 end를 감소시키고 작으면 start를 증가시킨다.
아주 전형적인 투포인터 문제이다.

✅ 코드에서 중요한부분

• 문제에서 여러개의 테스트케이스가 주어지나 그 수는 주어지지 않기 때문에 예외처리를 해준다.
• n와 레고의 길이 l은 단위가 다르기 때문에 x*10000000 를 해준다.
• 정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.
• 정답이 없을경우 danger을 출력해준다.