문제

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

정수 s와 t가 주어질때 s를 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하라
사용할수 있는 연산은 아래와 같다.
s += s (출력: +), s -= s (출력: -), s x= s (출력: x), s /= s (출력: /)

입력

• 첫줄에 s, t가 주어진다.
  • $1 \le s$, $t \le 10^9$

출력
s를 t로 바꾸는 방법을 출력한다. 같은경우 0을, 불가능한경우 -1을 출력한다.
방법이 여러가지라면 사전순으로 출력하는데 연산의 아스키 코드 순서는 *, +, -, / 이다.

정답코드

const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

function solution(s, t) {
  if (s === t) return 0;
  if (t === 0) return '-';

  const memo = new Set();
  const queue = [
    { now: s * s, str: '*' },
    { now: s + s, str: '+' },
    { now: 1, str: '/' },
  ];

  while (queue.length > 0) {
    const { now, str } = queue.shift();
    if (now === t) {
      return str;
    }
    if (memo.has(now)) {
      continue;
    }
    memo.add(now);

    if (now * now <= t) queue.push({ now: now * now, str: `${str}*` });
    if (now + now <= t) queue.push({ now: now + now, str: `${str}+` });
  }
  return -1;
}

const [s, t] = input();
console.log(solution(s, t));

코드설명

처음엔 dfs를 이용했지만 결국 bfs를 이용해 풀었다.
메모리 초과가 계속 났기 때문인데 생각해보니 계속 깊게 탐색할 필요가 없었다.
이는 나중에 설명하도록 하고 큐에 처음에 곱한값, 더한값, 1을 넣어준다

이 문제는 최소로 구하는 방법을 찾기위해 bfs로 탐색해서 s == t가 되자마자 탐색을 종료하면 된다.
근데 그냥 순서에 상관없이 탐색하면 결과가 문제가 원하는 정답과 달라진다.

문제는 사전순으로 앞의것을 출력하길 원하기때문인데 탐색할 큐에 넣을때
*, +, -, / 순으로 넣어준다면 만약 결과가 나오면 그게 사전순으로 가장 빠른 결과가 된다.

동일한 연산결과는 다시 탐색하지 않기위해 아래 코드를 추가했다.
사전순으로 빠른 연산을 했다면 뒤에서는 다시 볼 필요가 없기 때문이다.

if (memo.has(now)) {
  continue;
}
memo.add(now);

그리고 그러지 않으면 무한루프에 빠져 시간초과가 나오기 떄문이기도 하다.
큐에 나누기 했을경우 now를 1로 넣어줬기 때문에 1*1이 무수히 많이 반복돼서 시간초과가 나온다.

아 마지막으로 now x now , now + now가 t 이하인경우만 큐에 넣어줬는데
t보다 커질경우 더이상 답에 접근할수 없기 때문에 이렇게 처리해줬다.

첫번째 시도

아마 dfs로 접근해서 틀린 이유가 가장 클것같다.
t가 2의 제곱일경우 /+를 미리 더한 후에 s == t 일때까지 while을 돌려줬다.
t가 2의 제곱이 아닐경우 dfs로 탐색을 진행한 후에 모든 결과를 모아서 길이가 가장 짧은 결과만 추렸다.
그러고서 사전순으로 정렬후에 출력을 해줬는데 이러면 메모리 초과가 나온다.
그리고 연산도 *, +, -, / 를 모두 해줬는데 그럴 필요가 없었다.

두번째 ~ 마지막이전 시도

dfs로 접근했던 방법을 bfs로 변경했다.
그러니 더이상 시간초과는 뜨지 않았지만 정답이 틀렸다고 나온다.

반례가 뭐가 있을까 생각을 해보니 s=7, t=32일때가 있었다.
원래 정답은 /+**+인데 /+***가 나와버렸다.

s=1, t=1000 일때도 무한루프에 빠진다
아래의 코드 때문이다.

if (s !== 1 && t == (t & -t)) {
  // s가 2의 제곱근이 아닌경우
  if (!(s == (s & -s))) {
    result = result.concat('/+');
    s = 2;
  }
  while (s !== t && s <= t) {     
    s *= s;
    result = result.concat('*');
  }
}

이 코드로 접근해서 안되면 bfs로 접근 하는데 이부분이 잘못됐다.
이유는 두개 있는데 while이 끝나고 *가 하나 붙은상태로 탐색을 시작했고
그렇게 변경된 s를 큐에 넣어주지 않고 탐색을 시작했기 때문이다.
그래서 그냥 저 부분을 없애버리기 위해 한번더 일반화시켰다.

2의 제곱을 따로 처리해 주지 않고
제일 처음 큐에 { now: 1, str: '/' } 이런식으로 아예 1로 시작하는 부분을 넣어주는거다.
중복탐색때문에 저렇게 따로 처리해줬는데 이미 들렀던곳은 메모이제이션 해준다면 이도 해결되기 때문에
정답일거라 생각하고 코드를 수정한 결과는!!

드뎌 정답이다