백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 12852 , 1로 만들기 2 [BFS, DP]

백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 12852 , 1로 만들기 2 [BFS, DP]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

 

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

12852번: 1로 만들기 2

 

 

문제풀이 소감 🧑‍💻

푸는 방법이 여러가지인 것같은데 BFS로 풀려고 해본 문제이다.

시간초과는 발생하지않아 크게 어렵지는 않았다.

 

 

 

요구사항 📋

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 

X가 1이되면 종료한다.

 

연산을 하는 횟수의 최솟값을 출력
그리고, 그 과정을 출력

 

 

주의 ❗

 

for 문 내에서 if 문을 다 걸어주지 않고 i3 으로 나누어 지던가 2로나누어지던가 둘 중 하나만 해당되게 else if 문으로 조건을 걸어버렸더니 틀렸었다.

 

이렇게 하면 3과 2를 모두 약수로 가지고 있는 숫자들을 정확하게 계산하지 못하는 이유 같다.

 

따라서 모두 if 문으로만 걸어서 경우의 수를 탐색하게 하자.

 

 

 

 

 

해결 전략 📝

역추적도 필요하기때문에 2차원 배열을 N+1 크기만큼 선언한다.

 

이후 2번 인덱스부터 이전 값들을 저장해 나아간다.

과정을 수행하면서 이전 숫자를 같이 저장해서 최종 값에 도달했을때 역으로 타고 들어가 두번째 출력값들을 찾아준다.

 

 

 

 

기능 목록 📲

 

1. 1을 뺀다 => 1을 더한다.

 

track[i][0] = Math.min(track[i - 1][0] + 1, track[i][0]);
    if (track[i][0] === track[i - 1][0] + 1) {
      track[i][1] = i - 1;
    }

 

첫번째 기능 1을 빼는 것을 역으로 1을 더해나아간다.

 

만약 1을 더했을때 누적 연산횟수가 더 적다면, 더하기전 숫자를 더한 숫자의 1번인덱스에 저장한다.

 

이는 역추적을 위함이다.

 

 

2. 3을 나눈다 & 2를 나눈다

 

function divide(num, idx) {
    track[idx][0] = Math.min(track[parseInt(idx / num)][0] + 1, track[idx][0]);
    if (track[idx][0] === track[parseInt(idx / num)][0] + 1) {
      track[idx][1] = parseInt(idx / num);
    }
  }

 

num 파라미터로 3 혹은 2를 전달 받고 해당 숫자로 나눈 몫의 누적연산횟수를 비교한다.

 

만약, 그 값에 +1 한 값이 더 적다면, 그 몫을 이전 경로로 매겨준다.

 

 

 

 if (i % 3 === 0) divide(3, i);
 if (i % 2 === 0) divide(2, i);

나누어진다면 함수 호출.

 

 

3. 역추적

 

let result = [N];
let beforePlace = track[N][1];
while (beforePlace !== 0) {
  result.push(beforePlace);
  beforePlace = track[beforePlace][1];
}

track 배열의 N번 인덱스의 1번 인덱스 에는 이전 경로 숫자가 담겨있다.

 

이 값이 0이 나올때까지 역추적해서 경로를 저장해 나아간다.

 

최종적으로 이 값들을 순차적으로 출력시켜주면 된다.

 

 

 

 

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const input_N = Number(input);

function solution(N) {
  function divide(num, idx) {
    track[idx][0] = Math.min(track[parseInt(idx / num)][0] + 1, track[idx][0]);
    if (track[idx][0] === track[parseInt(idx / num)][0] + 1) {
      track[idx][1] = parseInt(idx / num);
    }
  }

  let track = Array.from({ length: N + 1 }, () => [Infinity, 0]);
  track[1] = [1, 0];
  for (let i = 2; i <= N; i++) {
    track[i][0] = Math.min(track[i - 1][0] + 1, track[i][0]);
    if (track[i][0] === track[i - 1][0] + 1) {
      track[i][1] = i - 1;
    }
    if (i % 3 === 0) divide(3, i);
    if (i % 2 === 0) divide(2, i);
  }
  let result = [N];
  let beforePlace = track[N][1];
  while (beforePlace !== 0) {
    result.push(beforePlace);
    beforePlace = track[beforePlace][1];
  }
  console.log(track[N][0] - 1);
  console.log(result.join(" "));
}

solution(input_N);