[BOJ]1463번: 1로 만들기(java, c++)

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

1463번: 1로 만들기

 

방법 1: Top-down

import java.io.*;
 
public class Main {
 
    public static int[] arrCount;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
 
            int num = Integer.parseInt(br.readLine());
 
            arrCount = new int[num + 1];
 
            int result = calculate(num);
 
            System.out.println(result);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    
    public static int calculate(int num) {
 
        if (num == 1) {
            return 0;
        }
        
        if (arrCount[num] > 0) {
            return arrCount[num];
        }
        
        arrCount[num] = calculate(num - 1) + 1;
        
        if (num % 3 == 0 ) {
            int temp = calculate(num / 3) + 1;
            if (arrCount[num] > temp) {
                arrCount[num] = temp;
            }
        }
        
        if (num % 2 == 0) {
            int temp = calculate(num / 2) + 1;
            if (arrCount[num] > temp) {
                arrCount[num] = temp;
            }
        } 
        return arrCount[num];
    }
}

 

c++소스

#include <iostream>
 
using namespace std;
 
const int MAX = 1000000;
int M[MAX + 1];
 
// 점화식 : D[n] = min(D[n - 1] + 1, D[n / 2] + 1, D[n / 3] + 1)
int make_one(int n)
{
    // 종료조건
    if (n == 1)
    {
        return 0;
    }
 
    if (M[n] > 0)
    {
        return M[n];
    }
 
    // 10->9->3->1 과 같은 반례가 있을 수 있으므로,
    // 1 ~ N 까지의 모든 경우의 수를 미리 저장
    M[n] = make_one(n - 1) + 1;
    
    // 현재 저장된 값 > 새로 구한 값일 때, 갈음하기
    if (n % 2 == 0)
    {
        int temp = make_one(n / 2) + 1;
        if (M[n] > temp) M[n] = temp;
    }
 
    if (n % 3 == 0)
    {
        int temp = make_one(n / 3) + 1;
        if (M[n] > temp) M[n] = temp;
    }
 
    return M[n];
}
 
int main()
{
    int n;
    cin >> n;
 
    make_one(n);
 
    cout << M[n];
 
    return 0;
}

 

 

방법 2: Bottom-up

import java.io.*;
 
public class Main {
 
    public static int[] arrCount;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
 
            int num = Integer.parseInt(br.readLine());
 
            arrCount = new int[num + 1];
 
            int result = calculate(num);
 
            System.out.println(result);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    
    public static int calculate(int num) {
        
        arrCount[1] = 0;
        
        for (int i = 2; i < arrCount.length; i++) {
            arrCount[i] = arrCount[i - 1] + 1;
            
            if (i % 3 == 0 && (arrCount[i] > arrCount[i / 3] + 1)) {
                arrCount[i] = arrCount[i / 3] + 1;
            }
            
            if (i % 2 == 0 && (arrCount[i] > arrCount[i / 2] + 1)) {
                arrCount[i] = arrCount[i / 2] + 1;
            }
        }
        
        return arrCount[num];
    }
}

 

 

1. 먼저 점화식을 세울 것

2. 탑다운 방식이라면 종료조건 & 메모이제이션  필수!

    - 문제에 따라서 이미 계산한 항은 다시 계산하지 않기도 하고, 다시 계산해서 덧씌우기도 한다.

 

 

TIP1

점화식 : D[n] = min(D[n - 1] + 1, D[n / 2] + 1, D[n / 3] + 1)

 

 

 

TIP2

탑다운이 동작하는 방식(메모이제이션X)

 

탑다운이 동작하는 방식(메모이제이션O)

탑다운(재귀)은 점화식을 그대로 구현한 방식이다. 

D[n] = min(D[n - 1] + 1, D[n / 2] + 1, D[n / 3] + 1)

위 점화식에서, n이 6일때를 대입하여 탑다운 동작 방식을 식으로 쓰면

 

D[6] = min(D[5] + 1, D[6 / 2] + 1, D[6 / 3] + 1)

D[5] = min(D[4] + 1) 

D[4] = min(D[3] + 1, D[4 / 2] + 1)

D[3] = min(D[2] + 1, D[3 / 3] + 1)

D[2] = min(D[1] + 1, D[2 / 2] + 1)

D[1] = 0

 

메모이제이션을 하지 않는다면 

재귀함수는 모든 경우마다 종료조건( n == 1 )까지 다시 호출해야 한다.

따라서 다이나믹 문제를 풀때는 가급적 메모이제이션을 통해서 효율성을 높여야 한다.   

 

 

 

TIP3

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

 

문제의 조건은 위 순서로 주어져지만, 우선순위는 반대로

 

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

 

가 되어야 한다.

 

왜?

10->9->3->1 과 같은 반례가 있을 수 있으므로,

1~N까지의 모든 경우의 수를 미리 저장해두어야 한다. 

그리고나서 더 적합한 경우의 수가 나오면 덮어쓰기 한다.