백준 1463 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

 

EXPLANATION

 

 

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

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

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

 

 

숫자 i가 가지는 최소 연산 횟수를 dp[i]라고 하면,

dp[i]가 가질 수 있는 값은

1) dp[i - 1] + 1
2) i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1
3) i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1

이고, 이중에서 최솟값을 구하면 된다.

 

이를 코드로 나타내면

int minValue = dp[i-1]+1;
if(!(i%3)) minValue = min(minValue, dp[i/3] + 1);
if(!(i%2)) minValue = min(minValue, dp[i/2] + 1);
dp[i] = minValue;

 

짧게 바꾸면

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

 

 

 

숫자 i가 가지는 최소 연산 횟수가 dp[i]이므로

i는 1부터 시작한다.

base: dp[1] = 0

 

 

 

i가 2와 3 모두로 나누어 떨어질 때 3으로 나누는 게 항상 최적화된 값을 얻을꺼 같지만 아니다.

ex)

입력: 642

1. 처음에 2로 무조건 나누고, 그 다음부터는 최적의 방법대로

642 --무조건 2로 나누기--> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1
총 10번의 연산 필요

2. 처음에 3으로 무조건 나누고, 그 다음부터는 최적의 방법대로

642 --무조건 3으로 나누기--> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 3 -> 1
총 11번의 연산 필요

따라서, 경우에 따라서는 2와 3으로 모두 떨어지는 수라도 2로 나누는 게 더 최적일 수 있다. 그러므로 항상 3가지의 연산을 모두 고려해 줘야 한다.

 

 

 

CODE

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int N;
    cin >> N;
    int dp[N+1] = {};	//for [1, N]
    dp[1] = 0;
    for(int i =2; i<= N; i++){
        dp[i] = dp[i-1]+1;
        if(!(i%2)) dp[i] = min(dp[i], dp[i/2] + 1);
        if(!(i%3)) dp[i] = min(dp[i], dp[i/3] + 1);
        //min(dp[i-1]+1, dp[i/2]+1, dp[i/3]+1)
    }    
    
    cout << dp[N] << "\n";

}