[백준] 1463: 1로 만들기 - JS (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

알고리즘 문제를 풀 때, 1초에 CPU가 계산하는 양은대략적으로 10^6~ 10^8 정도이다.

이 문제에서 입력은 최대 10^6 이므로 시간 복잡도가 O(N)인 알고리즘으로 풀 수 있다는 얘기이다.

 

나는 이 꼼수?를 이용하여 풀어봤다.

 

dp = [0, 0] 초기 설정을 해주고 for문으로 2부터 10^6 까지 다 dp 배열에 넣어버리는 것이다.

for(let i = 2; i <= 10**6; i++)

 

 

그리고 그 안에 이제 if문을 활용하여 식을 만들어 보자.

 

 

dp[i] = dp[i - 1] + 1;

 

먼저 -1 에 대한 식을 먼저 작성해 주었다.

그리고 Math.min을 통해서 dp[i]에 가장 작은 수가 넣어지게 하였다.

 

	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);
	};

 

+1을 해주는 이유는 i/2혹은 i/3을 해주었기 때문이다.

 

 

  풀이

 

제출코드

 

const N = parseInt(require('fs').readFileSync('/dev/stdin').toString().trim());

  const dp = [0, 0];  // 초기값 0, 0


for(let i = 2; i <= 10**6; 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]);