[백준] 3649번 : 로봇 프로젝트

3649번: 로봇 프로젝트

3649번: 로봇 프로젝트

🤔 문제분석

이분탐색 혹은 투포인터로 문제를 해결 할 수 있으나 이분탐색 풀이법으로 문제를 해결하였습니다. 레고를 사이즈 오름차순으로 정렬한뒤에 순회하는데 i번째를 순회할때 (i+1, N)까지 이분탐색을 통하여 (arr[i] + arr[mid])값이 블록의 사이즈랑 맞을경우는 후보에 두고, 블록 사이즈보다 작다면 start를 mid+1로 크다면 end를 mid-1로 두어 좁혀가며 탐색을 한다.

후보들을 모두 구한뒤에 그중에서 절대값의 차가 가장 높은 값을 갱신하여 출력하면된다.

투포인터 방법으로는 left를 0 right를 N-1로 둔 뒤에, 합 값이 레고사이즈보다 크다면 right를 감소시키고, 레고 사이즈보다 작다면 left값을 증가시켜가면서 레고사이즈랑 같은 값을 찾은뒤에 그중 절대값의 차가 가장 큰 값을 찾으면 된다.

💻 코드

import sys
input = sys.stdin.readline

while True:
    try:
        x = int(input())
        n = int(input())
        lego = []
        for _ in range(n):
            lego.append(int(input()))
            
        lego.sort()
        max_cost = -1
        l1, l2 = -1, -1
        checker = x * (10**7)
        for i in range(n):
            start = i+1
            end = n-1
            while end >= start:
                mid = (start+end)//2
                cost = lego[i] + lego[mid]
                if cost == checker:
                    if abs(lego[i] - lego[mid]) > max_cost:
                        max_cost = abs(lego[i] - lego[mid])
                        l1, l2 = i, mid
                        
                    break
                elif cost > checker:
                    end = mid - 1
                else:
                    start = mid + 1
        
        if l1 != -1 and l2 != -1:
            print("yes", lego[l1], lego[l2])
        else:
            print("danger")
    except:
        break

🎯 피드백 및 개선사항

골드5 정도의 정렬 알고리즘 문제는 이제 쉽게 풀리는것 같습니다. 어떠한 유형이 나오고 어떻게 접근해야할지 감이 잡혀나아가고 있습니다.