[백준] 1463번: 1로 만들기 - Node.js (자바스크립트)

1. 문제 ㅡ 1463번: 1로 만들기 (난이도: Silver III)

1463번: 1로 만들기

2. 풀이 ㅡ Node.js (자바스크립트)

const num = +require('fs').readFileSync('/dev/stdin').toString();
const DP = new Array(num + 1).fill(0);

for (let i = 2; i <= num; i++) {
  DP[i] = DP[i - 1] + 1;

  if (i % 2 === 0) DP[i] = Math.min(DP[i], DP[i / 2] + 1);
  if (i % 3 === 0) DP[i] = Math.min(DP[i], DP[i / 3] + 1);
}

console.log(DP[num]);

 

2-1. 풀이 설명

입력으로 주어진 정수가 1이 되기까지 필요한 최소 연산 횟수를 구하는 DP문제다. 

 

아래 규칙에 따라 2부터 N까지, 각 숫자를 1로 만드는 최소 연산 횟수를 계산하여 'DP' 배열에 저장해두었다.

1. 어떤 수든 우선 이전 값 + 1을 넣는다 (이전 수를 1로 만들기 위해 필요한 연산 횟수 + 1 만큼의 연산을 수행하면 현재 수를 1로 만들 수 있음) 
2. 2로 나눠지는 경우 DP 배열에 (i / 2) OR 1번에서 계산된 값 중 더 작은 값을 DP 배열에 저장한다
3. 3으로 나눠지는 경우 DP 배열에 (i / 3) OR 1번에서 계산된 값 중 더 작은 값을 DP 배열에 저장한다

마지막에 DP 배열의 N번째에 위치한 값을 출력해주면 된다.