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

X를 1로 최소한의 연산으로 만드는 문제입니다.

다이나믹 프로그래밍을 이용해서 풀었습니다.

 

memo배열에 각각의 숫자에 대한 연산 횟수를 저장하고

1. 3으로 나누었을 때

2. 2로 나누었을 때

3. 1을 뺐을 때

이 세가지 경우의 수를 비교해서 가장 작은 연산 횟수인 방법 +1을 현재 배열에 저장합니다.

만약 연산횟수가 동일하다면 숫자가 더 적어지는 방법을 우선순위합니다. ( x/3 > x/2 > x-1 )

이렇게 찾고자하는 값이 될때까지 반복하여 문제를 풉니다.

 

#include  
using namespace std; 

int memo[1000000]; 
int num; 
#define MAX 987654321; 
    
void func(int x)  
{ 
    int a = MAX; 
    int b = MAX; 
    int c = MAX; 

    if (x > num) { 
        return; 
    } 
    if (x % 3 == 0) { 
        a = memo[x / 3]; 
    } 
    if (x % 2 == 0) { 
        b = memo[x / 2]; 
    } 
    c = memo[x - 1]; 

    if (a <= b && a <= c) { 
        memo[x] = memo[x / 3] + 1; 
    } 
    else if (b <= c) { 
        memo[x] = memo[x / 2] + 1; 
    } 
    else { 
        memo[x] = memo[x - 1] + 1; 
    } 

    func(++x); 
} 

int main(int argc, char *argv[]) 
{ 
    cin >> num; 
    memo[0] = 0; 
    memo[1] = 0; 
    memo[2] = 1; 
    memo[3] = 1; 

    func(4); 
    cout << memo[num]; 
    return 0; 
}