[백준 - Python] 14395 - 4연산

0. 문제 링크

 

 

https://www.acmicpc.net/problem/14395

14395번: 4연산

---

1. 풀이 방법

 

 

해당 문제를 보면 알겠지만, 일단 뺄셈 연산은 쓰면 안 된다.

나눗셈 연산도 t가 2의 거듭제곱꼴이 아니라면 쓰면 안 된다.

사실상 연산은 +와 *만 하는 셈

그러면 숫자는 항상 우상향을 한다.

그래서 나는 t가 2의 거듭제곱꼴이 아니면 +와 *만 했고, 2의 거듭제곱이라면 / 연산도 추가했다.

근데 틀렸다.

솔직히 말해서 왜 틀린지 도저히 못찾았다.

결국 구글링하니까 t가 2의 거듭제곱인지 상관 없이 / 연산도 넣는 것이다.

실제로 그렇게 하니까 정답이 됐다.

아무튼...방문 처리는 check 라는 배열에 넣었다.

근데 진짜 왜 틀린건지 모르겠다.

아마 내가 찾지 못한 그런 반례가 있나보다 .. ㅠ 

---

2. 코드

 

 

from collections import deque

n1, n2 = map(int, input().split())
dq, op, check = deque(), ['*', '+'], set()      # 빼기 연산은 필요 없음
if n1 == n2:        # 같다면 끝
    print(0)
    exit(0)
elif n2 == 1:       # n2가 1이라면 나눗셈 하나만 하면 됨
    print('/')
    exit(0)
dq.append([n1, ''])
while dq:
    n, root = dq.popleft()
    for i in range(2):      # 0이면 곱셈, 1이면 덧셈
        nn = n * ((1 - i) * n + i * 2)      # n * n이거나 n + 2인 경우를 분별함
        if nn in check: continue        # 이미 방문한 경우
        if nn < n2:     # nn은 항상 우상향이기 때문에 n2보다 크면 정답이 아님
            dq.append([nn, root + op[i]])
            check.add(nn)
        elif nn == n2:      # 같다면 반환
            print(root + op[i])     # 먼저 root가 더 적고, 더 높은 우선순위를 가지고 있음
            exit(0)
    if 1 in check:      # 1도 방문했는지 확인해야 함 (?)
        continue
    dq.append([1, '/'])      # 1도 탐색해봐야 함
    check.add(1)
else:
    print(-1)

---

3. 마무리