백준 14395 4연산

875 단어 BFSBFS
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 + '/'))
  1. 메모리 초과 문제로 check를 list말고 set으로
  2. 0으로 나눌 수 없는 문제 때문에 배열에 x/x대신 0 을 넣어줬고 밑에서는 x!=0 조건을 추가
  3. 문제 조건에 가능한 연산이 여러 개이면 아스키코드 연산 순 (사전 순 )으로 한다고 했으니 if 문의 순서 또한 중요하다

시간 복잡도 계산

좋은 웹페이지 즐겨찾기