[백준 알고리즘] Node.js 12852. 1로 만들기 2

1. 문제

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

12852번: 1로 만들기 2

 

2. 풀이

1) DP를 이용하여 푸는 문제였다. 

2) 주어진 숫자보다 하나 큰 배열을 만들고 배열 안에 연산되는 횟수와 배열을 넣을 생각을 했다. 

ex) [0, []], [0,[1]]... 이런 방식으로 [ 연산횟수, [ 계산된 값들 ] ]

const n = +require('fs').readFileSync('/dev/stdin').toString().trim();
const dp = Array.from({length : n+1}, () => [0,[]]) // dp 배열 만들기

// 첫번째 값들 설정
dp[1][0] = 0 
dp[1][1] = [1]

// 2번째 값부터 설정.
for(let i = 2; i < n+1; i++){
  dp[i][0] = dp[i-1][0] + 1;
  dp[i][1] = [...dp[i-1][1],i]
	
  // 만약 2로 나누어 떨어지고, 기존 연산 회수와 dp[i/2][0]의 연산회수 + 1 비교 후, 최솟값으로 변환.
  if(i % 2 === 0 && dp[i][0] > dp[i / 2][0] + 1){
    dp[i][0] = dp[i/2][0] + 1;
    dp[i][1] = [...dp[i / 2][1], i]
  }

  // 만약 3으로 나누어 떨어지고, 기존 연산 회수와 dp[i/3][0]의 연산회수 + 1 비교 후, 최솟값으로 변환.
  if(i % 3 === 0 && dp[i][0] > dp[i / 3][0] + 1){
    dp[i][0] = dp[i/3][0] + 1;
    dp[i][1] = [...dp[i / 3][1], i]
  }
}

//출력
console.log(`${dp[n][0]}\n${dp[n][1].reverse().join(" ")}`)

 

3. 정리

- 배열별로 담을 생각을 했지만 계속 실패해서 파이썬으로 푸신 분의 자료를 참고하여 해결했다.

https://wooono.tistory.com/637

 

- 다른 nodejs 로 푸신분은 queue를 이용하여 해결하셨다.

https://lhoiktiv.tistory.com/636

 

- 어렵당. DP관련 기본 문제 같은 류를 다시 해결해봐야겠다. 아직 미숙하다.