[백준/Python] 3649 로봇 프로젝트

문제링크 : https://www.acmicpc.net/problem/3649 

3649번: 로봇 프로젝트

 

고려했던 방법들

1. 조합으로 풀수 있을까? 생각해보았지만 n이 1000000 까지 이므로 O(2^1000000)이 되어버려 조합은 사용할 수 없다.

2. 두번째는 레고 조각의 길이를 key 로 하는 해쉬맵을 만들어 [구멍의 너비 - 레고블럭 하나] 의 값이 해쉬맵에 존재하는지 판단하는 방법이 떠올랐다. 하지만 메모리 초과가 났다.

3. 세번째로는 이분 탐색으로 풀었는데 방향은 맞았으나 로직을 잘못짜서 풀지 못했다. 내가짠 로직에서는 시간복잡도가 O(N * logN) 이였는데, 이문제에서 n = 1000000 이고 log N 은 6 이므로 시간복잡도는 통과할 수 있었지만 메모리 초과가 났다.  잘못된 이분탐색 풀이

 

이분탐색을 배열의 값으로 시도 할 수도있지만 index로도 할 수 있음을 알 수 있었다.

문제풀이

이분탐색 문제이고 자바스크립트로는 풀 수 없는 문제였다. (백준에 자바스크립트로 솔브한 사람이 없다.)

따라서 파이썬으로 풀었다.

 

1. 레고 조각을 저장한 배열을 생성한 후 정렬한다. (이분탐색을 사용하기 위해서)

2. lt = 첫번째 인덱스 , rt = 마지막 인덱스로 두고 이분탐색을 한다.

    2-1. 구멍난 너비 === 레고조각배열[lt] + 레고조각배열[rt] 가 같아지면 구멍을 막을 수 있는 조각이므로 print 한다.

    2-2. 구멍난 너비 >  레고조각배열[lt] + 레고조각배열[rt]  라면 lt + 1 한다.

    2-3. 구멍난 너비 <  레고조각배열[lt] + 레고조각배열[rt]  라면 rt - 1 한다.

 

이때 주의할 점은 while 문의 조건이 다음과 같다는 것이다.

   while lt < rt:

등호를 붙힌다면 lt === rt 인 같은 레고조각 두개로 구멍을 막는 경우가 발생한다.

 

import sys
input = sys.stdin.readline

NANO_METER = 10_000_000
answer = []

while True:
    try:
        widthHole = int(input()) * NANO_METER
        numberOfLegoPeices = int(input())
        legoPeices = []

        legoPeices = [int(input()) for _ in range(numberOfLegoPeices)]

        legoPeices.sort()

        lt, rt = 0, numberOfLegoPeices-1
        flag = True

        while lt <= rt:
            if widthHole == legoPeices[lt] + legoPeices[rt]:
                print('yes %d %d' %(legoPeices[lt], legoPeices[rt]))
                flag = False
                break
            elif widthHole > legoPeices[lt] + legoPeices[rt]:
                lt += 1
            else:
                rt -= 1

        if flag:
            print('danger')
    except:
        break