[백준 node.js] 1463번_1로 만들기

🚩 1463번_1로 만들기 실버3

 

📖 문제 설명 : 정수 N이 주어졌을 때 주어진 조건에 따라 1로 만든다. 이때 연산을 사용하는

횟수의 최솟값을 구해라.

 

💡 DP 유형이므로 i번째를 구할 때, i 이전의 값들을 이용해서 해결한다.

 

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()

let N = Number(input)
let answer = Array.from(Array(N + 1), () => 0)
answer[2] = 1
answer[3] = 1

for (let i = 4; i <= N; i++) {
  // -1 하는 경우 -> 이전 값의 경우의 수 +1
  answer[i] = answer[i - 1] + 1
  // 3으로 나누어지는 경우 -> 3으로 나눈 값의 경우의 수 +1
  if (i % 3 === 0) {
    answer[i] = Math.min(answer[i], answer[i / 3] + 1)
  }
  // 2로 나누어지는 경우 -> 2로 나눈 값의 경우의 수 +1
  if (i % 2 === 0) {
    answer[i] = Math.min(answer[i], answer[i / 2] + 1)
  }
}

console.log(answer[N])

👨‍💻 코드 설명

숫자 2와 3은 1로 가는 경우의 수가 한 가지이다. 4의 경우에는 3으로 가는 경우의 수 + 3이 1로 가는 경우의 수의 합이다. 또 숫자 5는 4로 가는 경우의 수 + 4가 1로 가는 경우의 수가 되고,

숫자 6은 5로 가는 경우의 수 + 5가 1로 가는 경우 수이다.

 

이를 점화식으로 나타내면 다음과 같다.

answer[i] = answer[i - 1] + 1

 

하지만 숫자 6은 2로 나누어지므로 2로 나눈 값에 -1을 통해 1로 만들 수 있기 때문에

2로 나눈 몫 + 1이 된다. 이들 값 중 최솟값으로 지정해 주면 된다.

if (i % 2 === 0) {
    answer[i] = Math.min(answer[i], answer[i / 2] + 1)
  }

3의로 나누어지는 경우도 위와 동일하게 작성하면 된다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.