[DynamicPrograming]BAEKJOON1463 - 1로 만들기

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

 

 

이 문제는 백준에서 동적계획법(다이나믹 프로그래밍)문제 중에서는 가장 위에 있는 문제이며 가장 유명한 문제이다.

난이도는 동적계획법중에서 가장 쉬운 편이기에 초보자들에게 많이 추천받는 문제이기도 하다.

 

시간 제한은 2초로 널널한편, 동적계획법만 효율적이게 작동한다면 무조건적으로 해결되는 시간이다.

또한 메모리제한도 256메가는 아니지만 신경쓸 정도는 아니다. 정답률은 32퍼로 동적계획법이라는점, 사람들이 많이푼다는점.

두개를 종합해 봤을 때 정답률 역시 높은 편이라고 볼 수 있다.(단 일반적으로 32퍼는 낮은 확률에 속한다.)

 

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

 

이 문제는 위의 세가지 경우를 반복한다.

 

즉 어떤 수 X가 주어졌을 때 위의 위의 연산을 통해서 1을 만드는데 그중에서 최솟값을 출력하면된다.

 

7을 예시로 들어보자.

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

 

7->(1)불가능
7->(2)불가능
7->(3)6->(1)2->(1)불가능
7->(3)6->(2)3->(1)1
7->(3)6->(3)5->(1)불가능
7->(3)6->(3)5->(2)불가능
7->(3)6->(3)5->(3)4->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(2)1
7->(3)6->(3)5->(3)4->(2)2->(3)1
7->(3)6->(3)5->(3)4->(3)3->(1)1
7->(3)6->(3)5->(3)4->(3)3->(2)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(1)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(2)1
7->(3)6->(3)5->(3)4->(3)3->(3)2->(3)1

 

7이 가능한 경우의 수를 한번 보도록하자.

불가능한 경우를 도달한것을 센다면 7의 경우15가지, 불가능한 경우를 도달한 것을  뺀다면 6가지의 경우의 수 이다.

시간복잡도는 항상 최악으로 계산하는데 보면 알겠지만 3^7개까지의 경우의 수를 나열하므로

시간복잡도 계산시에는 O(3^n)로 계산하게 된다.

다만 실제로는 저 시간복잡도에 한참 못미치는데 그 이유는 실제 숫자가 2나 3으로 안나눠지는 경우가 아주 많기 때문에

기하 급수적으로 경우의 수가 줄어들긴 한다.

 

일단 중요한건 그냥 완전탐색(브루트포스로)문제를 풀줄 알아야한다.

그러면 위의 시간복잡도로 풀 수 있다.

 

그러면 우리는 공간복잡도를 이용해서 시간 복잡도를 줄 일 수 있다.
어떻게 시간을 줄이냐면 "중복된 계산"을 저장한 후 나중에 함수 호출해야할 경우 함수를 호출안하고 계산된 값을 주는 것이다.

즉 일종의 캐싱전략이고 이를 메모이제이션이라고 부른다.

 

아래 예시를 보자

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

대괄호안의 숫자는 체크해야할 이전 값이다.

 

7을 예시로 생각하면 문제는 아래처럼 생각할 수 있다.

1이라면 최소값이 0이다.
-(1)은 불가능
-(2)은 불가능
-(3)은 불가능

2의 경우 최소값은 1이다.
-(1)은 불가능
-(2)의 결과값[1] : 0
-(3)의 결과값[1] : 0
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

3의 경우 최소값은 1이다.
-(1)의 결과값[1] : 0
-(2)는 불가능
-(3)의 결과값[2] : 1
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

4의 경우 최소값은 2이다.
-(1)은 불가능
-(2)의 결과값[2] : 1
-(3)의 결과값[3] : 1
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

5의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[4] : 2
-최소 값은 [4]의 2이므로 여기서 +1 해준다.

6의 경우 최소값은 2이다.
-(1)의 결과값[2] : 1
-(2)의 결과값[3] : 1
-(3)의  결과값[5] : 3
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

7의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[6] : 2
-최소값은 [6]의 2이므로 여기서 +1 해준다.

 

여러분은 분할정복기법으로 이 문제를 접근할 수 있어야한다.

7의 결과를 아는 것은 6의 최소값을 아는   것과 동일한 문제다.

6의 결과값을 아는 것은 5의 최소값을 아는 것과 동일한 문제이다.

이렇게 1까지 내려가면된다.

이를 코드로 구현하는 방법은 재귀와 for문이 있다.

마술 같게도 DP를 도입하면 시간복잡도는 O(n)이된다. 단 공간복잡도는 O(n)으로 늘어나게 된다.

 

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int f(int n) {
    if (n == 1) {
        return 0;
    } else {
        int min_val = INF;
        if (n % 3 == 0) {
            if (memo[n / 3] == -1) {
                memo[n / 3] = f(n / 3);
            }
            min_val = mi(min_val, memo[n / 3]);
        }
        if (n % 2 == 0) {
            if (memo[n / 2] == -1) {
                memo[n / 2] = f( n / 2);
            }
            min_val = mi(min_val, memo[n / 2]);
        }
        if (n - 1 >= 1) {
            if (memo[n - 1] == -1) {
                memo[n - 1] = f(n - 1);
            }
            min_val = mi(min_val, memo[n - 1]);
        }
        return min_val + 1;
    }
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
    }

    //logic
    {
        result = f(N);
    }

    //output
    {
        cout << result << endl;
    }

    return 0;
}

재귀로 푸는 방법은 위와 같다.

 

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
        memo[1] = 0;
    }

    //logic
    {
        for (int n = 2; n <= N; n++) {
            result = INF;
            if (n % 3 == 0) {
                result = mi(result, memo[n / 3]);
            }
            if (n % 2 == 0) {
                result = mi(result, memo[n / 2]);
            }
            if (n - 1 >= 1) {
                result = mi(result, memo[n - 1]);
            }
            memo[n] = result + 1;
        }

    }

    //output
    {
        cout << memo[N] << endl;
    }

    return 0;
}

for문을 이용해서 푸는 방법은 위와 같다.