백준) 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

 

---

풀이 과정

 

1.처음에는 알고리즘의 기본인 완전탐색으로 생각해봄.

2.레고조각들 중 2개를 뽑아 구멍의 너비랑 같게 해보려고함.

3.그런데 레고 조각의 수가 백만개 라고 작성되어있음

-> 2개 뽑으려면 O(N^2)이므로 시간이 폭파해버림 (약 1조....)

4.그러면 투포인터로 탐색해보자고 생각함.

5.투포인터로 하면 O(LogN)이므로 널널하므로, 구현만 문제없이 잘하면 되겠다고 생각했음

 

 

 

풀이 코드

import sys
input=sys.stdin.readline

while True:
    try:
        X=int(input())*10_000_000
        N=int(input())
        legos=[]
        for _ in range(N):
            legos.append(int(input()))
        legos.sort()

        start=0 
        end=N-1 

        # # end 구하기 
        # while(start<=end):
        #     mid=(start+end)//2 
        #     #부등호는 생각해보기
        #     if legos[mid]>=X:
        #         end=mid-1
        #     else:
        #         start=mid+1
        flag=True
        start=0
        while(start<end): 
            # print(start,end)
            if legos[start]+legos[end]==X: 
                print("yes "+str(legos[start])+" "+str(legos[end]))
                flag =False
                break 
            elif legos[start]+legos[end]>X: 
                end-=1 
            else:
                start+=1
        if flag:
                print("danger")
    except:
        break

 

0.조각들이 들어있는 배열을 sort로 오름차순 정렬을 함

1.투포인터의 과정 진행 중 두 조각의 길이가 같아지면 정답을 출력하고 flag를 false로 바꾸고

   break를 하도록 구현했음.

---

Q1. flag는 뭔가요?

A1. 정답을 한번도 못만나면 danger로 출력하기 위한 변수입니다.

 

Q2. 문제 조건에 (정답이 여러 개인 경우에는 |ℓ1- ℓ2|가 가장 큰 것을 출력한다.) 는 어떻게 처리했나요?

A2. 어짜피 0번에 의해 sort로 배열이 정렬되어 있고, 투포인터는 배열의 양 끝에부터 줄어들으므로     가장 첫번쨰 정답이 |ℓ1- ℓ2|가 가장 큽니다.

---

2. 정답이 없으면 danger를 출력함.3.while(True)와 try - except로 여러개의 테스트 케이스를 입력받음.

 

 

 

 

실수했던 내용

import sys
input=sys.stdin.readline

while True:
    try:
        X=int(input())*10_000_000
        N=int(input())
        legos=[]
        for _ in range(N):
            legos.append(int(input()))
        legos.sort()

        start=0 
        end=N-1 

        # # end 구하기 
        # while(start<=end):
        #     mid=(start+end)//2 
        #     #부등호는 생각해보기
        #     if legos[mid]>=X:
        #         end=mid-1
        #     else:
        #         start=mid+1

        start=0
        while(start<end): 
            # print(start,end)
            if legos[start]+legos[end]==X: 
                print("yes "+str(legos[start])+" "+str(legos[end]))
                break 
            elif legos[start]+legos[end]>X: 
                end-=1 
            else:
                start+=1
            if start==end:
                print("danger")
    except:
        break

1.flag 대신에 투포인터가 끝나는 start==end 일 때 danger를 출력하려고 했었음.

2.그런데 문제 조건에서 레고 조각의 수가 (0 ≤ n ≤ 1000000) 이라,

n이 0과 1이면 while(start<end)가 실행을 안함.

3.그래서 danger가 출력이 안돼서 틀렸었음!! 

4.다음에도 안전하게 flag를 사용하자는 교훈