본문 바로가기

알고리즘/알고리즘 문제

DP- 1로 만들기

<문제>

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

 

- 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제

 

[Top-Down 방식]

int go (int n){
    if(n==1) return 0;
    if(d[n] > 0) return d[n];
    d[n] = go(n-1) + 1;
    if(n%2 == 0){
        int temp = go(n/2) + 1;
        if(d[n] > temp) d[n] = temp;
    }
    if(n%3 == 0){
        int temp = go(n/3) + 1;
        if(d[n] > temp) d[n] = temp;
    }
    return d[n]
}

 

[Bottom-Up방식]

d[1] = 0;
for(int i=2; i<=n; i++){
    d[i] = d[i-1] + 1;
    if(i%2 == 0 && d[i] > d[i/2] + 1){
        d[i] = d[i/2] + 1;
    }
    if(i%3 == 0 && d[i] > d[i/3] + 1){
        d[i] = d[i/3] + 1;
    }
}