[Baekjoon] 백준 1463번 1로만들기

Top-down

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

• 큰 문제를 작은 문제로 나누어서 풀이한 후 큰 문제의 정답을 알아내는 방법이다.
• 즉 n이 6인경우를 구할 때 d[6]을 알기 위해서는 작은 결과값인 d[5], d[4], d[2]의 결과 값 중 최소값을 찾아서 +1해주면 된다.
• d[5]는 d[4]+1 , d[4]는 d[3], d[2]의 최소값 +1, d[3]은 d[2], d[1]의 최소값 +1 이런식으로 재귀함수를 통해 가장 작은 결과값부터 시작하여 원하는 결과값 까지 도달한다.

Bottom-up

void bottom_up(int n) {
    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;
        }
    }
}

• 가장 작은단위의 문제부터 해결하는 방식이다.
• d[1]=0으로 고정되어있기 때문에 반복문은 2부터 n까지 수행하게되며 마찬가지로 d배열은 n이 1까지 만들기 위해 사용되는 연산의 횟수들 중 최소값을 갖게된다.1463번 1로 만들기 문제 풀이

주의사항

• 이번 포스팅은 굉장히 정신없이 작성되었기 때문에 작성자만 이해할 수 있는 문장들이 많을 수 있습니다...

문제

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

• 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제

입력
2
10

출력
1
3

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int d[1000001];
int n;

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

void bottom_up(int n) {
    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;
        }
    }
}

int main() {
    cin >> n;
    d[1] = 0;
    //top_down(n);
    bottom_up(n);
    cout << d[n] << "\n";
}

해결방법

• d[]는 memorization해놓는 공간으로서 이번 문제에서는 n을 1로 만드는데 사용되는 연산횟수의 최소값을 d[n]에 저장한다.
• N이 10인경우 D[10]을 구해서 출력하게 된다.
  이 때 다이나믹프로그래밍을 이용하면 Top-down방식과 Bottom-up방식 중 하나를 선택해서 풀이할 수 있다.
• 문제에서 사용할 수 있는 연산은 1을 빼거나, 3 혹은 2로 나누는 방법을 총 세가지이다.
• 따라서 d[n]의 값은 d[n/3]+1 , d[n/2]+1, d[n-1]+1 세 가지 값 중 최소값을 갖게된다.
• +1을 해주는 이유 : n이 6인경우 6-1=5, 6/2 =3, 6/3=2 각각 6이 5,3,2가 되기 위해서는 한 번의 연산을 수행하게 되기때문.

Top-down

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

• 큰 문제를 작은 문제로 나누어서 풀이한 후 큰 문제의 정답을 알아내는 방법이다.
• 즉 n이 6인경우를 구할 때 d[6]을 알기 위해서는 작은 결과값인 d[5], d[4], d[2]의 결과 값 중 최소값을 찾아서 +1해주면 된다.
• d[5]는 d[4]+1 , d[4]는 d[3], d[2]의 최소값 +1, d[3]은 d[2], d[1]의 최소값 +1 이런식으로 재귀함수를 통해 가장 작은 결과값부터 시작하여 원하는 결과값 까지 도달한다.

Bottom-up

void bottom_up(int n) {
    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;
        }
    }
}

• 가장 작은단위의 문제부터 해결하는 방식이다.
• d[1]=0으로 고정되어있기 때문에 반복문은 2부터 n까지 수행하게되며 마찬가지로 d배열은 n이 1까지 만들기 위해 사용되는 연산의 횟수들 중 최소값을 갖게된다.