문제
상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.
구멍의 너비는 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
코드
import sys
input=sys.stdin.readline
try:
while 1:
x=int(input())
x*=10000000
n=int(input())
array=[]
for _ in range(n):
temp=int(input())
array.append(temp)
array.sort()
i,j=0,n-1
flag=True
while i<j:
if array[i]+array[j]<x:
i+=1
elif array[i]+array[j]>x:
j-=1
else:
print('yes %d %d' %(array[i], array[j]))
flag=False
break
if flag:
print('danger')
except:exit()
생각 정리
import sys
input=sys.stdin.readline
try:
while 1:
x=int(input())
x*=10000000
n=int(input())
array=[]
for _ in range(n):
temp=int(input())
array.append(temp)
array.sort()
result=[]
for i in range(len(array)-1):
start=i+1
end=len(array)-1
while start<=end:
mid=(start+end)//2
if array[i]+array[mid]<x:
start=mid+1
elif array[i]+array[mid]>x:
end=mid-1
else:
result.append([array[i],array[mid]])
break
if len(result)==0:
print("danger")
else:
result_max=0
result1=0
result2=0
for i,j in result:
if result_max<abs(i-j):
result_max=abs(i-j)
result1=i
result2=j
print("yes",result1,result2)
except:exit()
맨 처음에 제출한 TLE코드 이다.
'문제풀이 > 이진탐색' 카테고리의 다른 글
[파이썬] [이진탐색] 백준 2343 기타레슨 (0) | 2022.01.22 |
---|---|
[파이썬] [이진탐색] 백준 7795 먹을 것인가 (0) | 2022.01.22 |
[파이썬] [이진탐색] 백준 16434 드래곤앤던전 (0) | 2022.01.21 |
[파이썬] [이진탐색] 백준 1365 꼬인전깃줄 (0) | 2022.01.20 |
[파이썬] [이진탐색] 백준 3079 입국심사 (0) | 2022.01.20 |