백준 14395 4연산
from collections import deque
s, t = map(int, input().split())
check = set()
ans = ''
q = deque()
q.append((s, ans))
check.add(s)
while q:
x, a = q.popleft()
if x == t:
print(a)
break
for y in [x+x, 0, x*x, 1]:
if y not in check:
check.add(y)
if y == x * x:
q.append((y, a + '*'))
if y == x + x:
q.append((y, a + '+'))
if y == x - x:
q.append((y, a + '-'))
if x != 0 and y == x/x:
q.append((y, a + '/'))
- 메모리 초과 문제로 check를 list말고 set으로
- 0으로 나눌 수 없는 문제 때문에 배열에 x/x대신 0 을 넣어줬고 밑에서는 x!=0 조건을 추가
- 문제 조건에 가능한 연산이 여러 개이면 아스키코드 연산 순 (사전 순 )으로 한다고 했으니 if 문의 순서 또한 중요하다
시간 복잡도 계산
Author And Source
이 문제에 관하여(백준 14395 4연산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gmlwlswldbs/백준-14395-4연산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)