[BOJ] 1로 만들기 1463번 C++

 

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

접근 방식

 

다양한 방식으로 풀이할 수 있겠지만,

N -> 1이 아닌 1 -> N을 만드는 방식으로 풀이 하였다

 

따라서 dp 배열을 1은 0, 2와3은 각각 1로 초기화하고

나머지 값들은 모두 최댓값인 자신의 값으로 초기화해주었다

 

그리고 다시 반복문을 돌면서 3의 배수인지 2의 배수인지 확인 후 더 작은 값을 비교해

dp 배열 값을 정해주었다.

 

마지막으로 이전값에서 +1한값과 비교해주었다.

 

 

 

코드

#include<bits/stdc++.h>
using namespace std;
int dp[1000005];

int main() {
    int N; cin>>N;

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for(int i=4; i<=N; i++) dp[i] = i;

    for(int i=4; i<=N; i++) {
        if(i%3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
        if(i%2 == 0) dp[i] = min(dp[i], dp[i/2] + 1);
        dp[i] = min(dp[i-1]+1, dp[i]); 
    }


    cout<<dp[N];

}