[BOJ] 4연산 (no.14395)

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

s = s + s; (출력: +)
s = s - s; (출력: -)
s = s s; (출력: )
s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

🤔 생각

• 우선순위가 있는 bfs다!

• 문제에 적혀있는 연산자 순서대로 if문을 배치해주면 된다.

• 빼기의 경우는 고려 안 해줘도 된다. (s,t 모두 1 이상이라고 범위가 명시되어있기 때문에, 굳이 0을 만들 필요가 없고 그게 최소가 될리도 없다.)

• 어떤 순서로 연산해왔는지를 기억해줘야 하기 때문에, 큐에 연산자 배열도 같이 넣어주면 되겠다.

• 캐시 배열의 범위를 얼마로 잡아야할지 명확하지가 않고, s,t의 최대 범위가 10의 9승이기 때문에 배열로 캐싱 체크는 불가능하다. (집합을 사용하면 된다!)

📌 내 풀이

import sys
input = sys.stdin.readline

def main():
    def bfs(s,t):
        if s == t: return 0
        bound = 10e9
        cache = {s}
        q = [(s, "")]
        cnt = 0

        while q:
            tmp = []

            for i,hist in q:
                if i == t: return hist

                if (op := i*i) <= bound and op not in cache: 
                    tmp.append((op, hist+"*"))
                    cache.add(op)

                if (op := i+i) <= bound and op not in cache: 
                    tmp.append((op, hist+"+"))
                    cache.add(op)

                if (op := 1) not in cache:
                    tmp.append((op, hist+"/"))
                    cache.add(op)
            
            cnt += 1
            q = tmp

        return -1


    s,t = map(int, input().split())
    print(bfs(s,t))

if __name__ == "__main__":
    sys.exit(main())

✔ 회고

• 최근에 walrus operator를 알게 되어서 활용해봤다!
• 버전이 높아야 해서 호환성이 좋진 않지만, 정말 예쁜 코드가 나온다