백준 1463 : 1로 만들기

💡기본 정보

유형
: DP
풀이 날짜
: 2025년 01월 29일 
풀이방법 한줄 요약
: 각 계산을 1을 빼는 것과 비교해서 더 적은 횟수인 것을 출력

 

💡문제에서 구해야 할 것

정수 X에 사용할 수 있는 연산은 다음과 같이 세가지
   - X가 3으로 나누어 떨어지면 3으로 나눔
   - X가 2로 나누어 떨어지면 2로 나눔
   - 1을 뺌

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

- 입력 : 첫째 줄에 1보다 크거나 같고 10^6 보다 작거나 같은 정수 N이 주어짐
- 출력 : 첫째 줄에 연산을 하는 횟수의 최솟값 출력

 

💡알고리즘 설계

- Bottom-up 방식으로 반복문 구현
- 1일때는 0
- 2의 배수면 2로 나눔
=> dp[N] = min(dp[N-1]+1,dp[N/2]+1)

- 3의 배수면 3으로 나눔

=> dp[N] = min(dp[N-1]+1,dp[N/3]+1)

=> dp[N] = min(dp[N-1]+1,dp[N/2]+1,dp[N/3]+1)

- 나머지는 1로 뺌
=> dp[N] = min(dp[N-1]+1)

각 계산을 1을 빼는 것과 비교해서 더 적은 횟수인 것을 출력

💡CODE

const fs = require("fs");
const N = Number(fs.readFileSync(0,"utf8").toString().trim());
const dp = new Array(N+1);

function one(){
    dp[1] = 0;
    for(let i = 2; i<=N;i++){
        if(i%2===0){
            dp[i]=Math.min(dp[i-1]+1,dp[i/2]+1);
        }
        if(i%3===0){
            dp[i]=Math.min(dp[i-1]+1,dp[i/3]+1);
        }
        if(i%3===0&&i%2===0){
            dp[i]=Math.min(dp[i-1]+1,dp[i/2]+1,dp[i/3]+1);
        }
        if(i%2!==0&&i%3!==0){
            dp[i]=Math.min(dp[i-1]+1);
        }
    }
    return dp[N];
}
console.log(one());

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

처음에는 그냥 점화식만 작성해서 틀림 

1을 빼서도 1을 도달할 수 있기 때문에 더 횟수가 작은 점을 .min()으로 해야함

 

💡 다른 풀이 or 기억할정보

-