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

 

 

문제를 보자마자 느낌이 왔다. 

아 이거.. 알고리즘이 필요하다!!!!!

 

처음에는 3부터 나누고, 2부터나눋고 -1 하면 되지 라고 생각했는데 천만의 말씀~

힌트에 떡하니 나와 있는 가르침을 보고 바로 돌렸다.

 

 

 

 

참고 풀이

const fs = require('fs');

let n = (fs.readFileSync('./dev/stdin') + '').toString().trim();
n = Number(n);

const DP = new Array(n + 1).fill(0);

for (let i = 2; i <= n; 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[n]);

풀이는 다이나믹프로그래밍 문제!

정말 다양한 방법의 가짓수를 다 계산해보고 최소 계산수를 구해야 하는데  그러기 위해서는 

n의 계산수를 구하기 위해서는 그 전의 값들의 최소 계산수들의 최소값들을 경쟁해서 올려줘야 하는 것이었다.

 

다이나믹 프로그래밍 푸는 팁에서도 간단히 설명을 해놨었는데

 

 

문제 풀이

 

예시로 10의 경우는 두 가지 경우를 돌려보고 최소값을 가지게 되는데

 

1) 9의 최소 계산수 + 1 

2) 2로 나눠지면  min(2로나눈값, 현재값)  min (DP[5]+1, DP[10])

2) 3로 나눠지면  min(3로나눈값, 현재값) 3으로 나눠지지 않음

 

여기서 +1 을 해주는 이유는

전의 값에서 10에 도달하기 직전의 최소 계산수에다 도달할 경우의 수(1)을 더해주기 때문이다.

 

 

< 반복문을 돌며  확인한 DP배열

 

DP[10] 에는

1) DP[9]+1   2+1= 3

2) DP[5]+1  4+1 = 5

중 최소값이 들어가기  때문에 3이 된다 

 

 

 

 

 

 

 

 

 

 

 

🥳 처음엔 절대 이해 못했는데 지금은 이해 되는걸  보니 알고리즘 실력(이라기보다 걍 노련함) 이 자라는 중인가보다!!

 

 

🔗 참고 블로그