[C++][DP] 백준 1463번 : 1로 만들기

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

백준 1463번 1로 만들기

 

🎨 코드

 

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    
    vector<int> dp(n+1 ,0);
    for(int i = 2; i<= n;i++)
    {
        dp[i] = dp[i-1]+1;
        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);   
    }
    cout<<dp[n];
    return 0;
}

 

🎯 풀이

 

문제 : 1로 만들기는 다이나믹 프로그래밍(DP)으로 해결하는 문제입니다.

 

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

 

모든 벡터의 숫자를 최소한 1로 만들어주기 위해 최소 연산 횟수를 저장합니다.

 

    if( i%3 == 0) dp[i] = min(dp[i],dp[i/3]+1);

 

만약 i가 3으로 나누어지면 dp[i]와 dp [i/3]+1과 비교하여 더 작은 값을 갱신합니다.

dp [i]는 위 코드를 통해  dp[i-1]+1 값을 가지고 있습니다.

 

    if( i%2 == 0) dp[i] = min(dp[i],dp[i/2]+1);

 

만약 i가 2로 나누어지면 dp [i]와 dp [i/2]+1과 비교하여 더 작은 값을 갱신합니다.

마찬가지로 dp [i]는 dp [i-1]+1 값을 가지고 있습니다.

 

글로 설명하면 이해가 어려울 수 있으니 n의 값이 10일 때를 가정하여 그림으로 설명하겠습니다.

 

1로 만들기 예시

10 입력 시 2부터 10까지 순차적으로 반복문을 실행하게 됩니다.

다른 값들과 달리 5, 7의 경우 나누어지지 않기 때문에 처음 초기화 하는 값으로 값이 정해집니다.

5와 7을 제외한 나머지 값들은 초기화를 한 뒤, 조건문을 통해서 값을 결정하게 됩니다.

 

풀이 과정을 보면 어렵지 않지만 다이나믹 프로그래밍은 익숙하지 않아서 어렵게 풀었던 문제였습니다.