[백준][Node.js] 1463번 : 1로 만들기

 

 

Algorithm

-  1로 만들기 -

 

---

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

 

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입출력 예시

 

문제 풀기

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();
input = Number(input);
let arr = [0, 0, 1, 1]; // 편의를 위해 0번째는 pass

for (let i = 4; i <= input; i++) {
	arr[i] = arr[i - 1] + 1;
	if (i % 3 === 0 && arr[i / 3] + 1 < arr[i]) {
		arr[i] = arr[i / 3] + 1;
	} else if (i % 2 === 0 && arr[i / 2] + 1 < arr[i]) {
		arr[i] = arr[i / 2] + 1;
	}
}

console.log(arr[input]);