[백준 1463][C++] 1로 만들기 (Silver 3)

[문제보기]

 1463. 1로 만들기

1463번: 1로 만들기

 

[풀이과정]

이 문제는 dp로 2로 나누기, 3으로 나누기, 1 빼기 3가지 경우에 대해서 최소를 갱신해나가면 되는 문제이다.

dp[2], dp[3]에 대해서는 최소의 경우는 1번이므로 정해두고 for문을 통해 나머지 숫자에 대해서 계산을 하면된다.

 

1로 뺄 때,

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

 

2로 나눌 때,

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

 

3으로 나눌 때,

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

 

이런 형식을 띄게 된다. 

[소스보기]

#include <iostream>
using namespace std;
int dp[1000001];

int main(){
    int temp = 0;

    dp[2] = 1;
    dp[3] = 1;
    int n;
    cin >> n;

    for(int i=4; i<=n; i++){
        dp[i] = dp[i-1] +1;

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

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

    
    cout << dp[n] << "\n";

}

 

[해결 과정 중 실수한 부분]