로봇 프로젝트
문제
상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.
구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.
지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.
다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)
다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.
출력
각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)
정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.
처음에 생각한 것은 이중 for 문 처럼 풀었는데 50%에서 계속 안되길래 찾아보니
테스트 케이스 개수가 정해지지 않고 여러 개가 들어 올 수 있는데 이를 처리하는 방법을 몰라서 헤맸다.
try except 문으로 해결을 하였고 그 다음에는 시간 초과가 발생하여 투 포인터를 사용하여 레고의 길이가 작으면 앞의 포인터를 늘리고 길면 뒤의 포인터를 줄이는 방식으로 하였다.
import sys
input = sys.stdin.readline
# 여러 테스트 케이스 받는 방법
while 1:
try:
x = int(input())
# 단위 변경
x = x * 10000000
N = int(input())
rego_list = []
for _ in range(N):
rego = int(input())
rego_list.append(rego)
rego_list.sort()
# 투 포인터(앞과 뒤에서 각각 시작)
one_pt = 0
two_pt = N - 1
# flag로 정답 유무 확인
flag = False
while one_pt < two_pt:
# x와 길이가 같으면 flag를 true
if rego_list[one_pt] + rego_list[two_pt] == x:
flag = True
break
# 길이가 짧으면 앞의 포인터를 늘리면 길이가 늘어나기 때문에 늘려준다.
elif rego_list[one_pt] + rego_list[two_pt] < x:
one_pt += 1
# 길이가 길다면 뒤의 포인터를 줄이면 길이가 줄어들기 때문에 줄인다.
else:
two_pt -= 1
# 정답이 있으면 yes 아니면 danger
if flag:
print('yes',rego_list[one_pt],rego_list[two_pt])
else:
print('danger')
except:
break
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
백준 1719(택배) - 참고 해결 (0) | 2022.02.19 |
---|---|
백준 14550(마리오 파티) - 해결 (0) | 2022.02.17 |
백준 21922(학부 연구생 민상) - 해결(pypy) (0) | 2022.02.06 |
백준 1490(자리수로 나누기) - 해결 (0) | 2022.02.06 |
백준 5710(전기 요금) - 해결 (0) | 2022.02.02 |