[백준 1463] 1로 만들기 - 자바

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

1463번: 1로 만들기

 

1. 풀이

---

이 문제는 DP 점화식을 사용하여 풀이하면 된다.

 

DP는 모든 경우의 수를 순회해야 할 때, 중복되는 순회를 빠르게 처리하기 위해 생긴 것이다. 그만큼 메모리가 차지하는 단점이 있긴하다.

 

D[n을 1로 만드는 횟수] =

(1) D[n/3을 1로 만드는 횟수] + 1

(2) D[n/2을 1로 만드는 횟수] + 1

(3) D[n-1을 1로 만드는 횟수] + 1

이 중에서 제일 작은 값을 골라서 D[n]에 저장하면 되는 것입니다.

 

즉 아래와 같은 코드가 됩니다.

memo[n] = memo[n-1] + 1; // n보다 1작은 수를 min이라고 가정합니다.
if(n % 2 == 0 ) // 만약 n 이 2로 나누어 진다면
	// n-1를 저장해둔 memo[n]과 n/2를 저장해둔 memo[n/2]중 최소값을 골라 저장합니다.
	memo[n] = min(memo[n], memo[n/2]+1); 
if(n % 3 == 0 )
	// n/2를 저장해둔 memo[n/2]과 n/3를 저장해둔 memo[n/3]중 최소값을 골라 저장합니다.
	memo[n] = min(memo[n], memo[n/3]+1);

처음엔 잘 이해가 안가지만, DP의 메모이제이션을 이용한 피보나치를 이해한다면 쉽게 이해할 수 있다.

 

2. 코드

---

2.1 Bottom-Up

import java.util.*;

public class Main {
	
	static int min(int a, int b) {
		if(a > b)
			return b;
		else
			return a;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[] memo = new int[num+1];
		
		memo[0] = memo[1] = 0;
		// Bottom-Up
		for(int i = 2; i <= num; i++) {
			memo[i] = memo[i-1] + 1;
			if(i % 2 == 0)
				memo[i] = min(memo[i], memo[i/2] + 1);
			if(i % 3 == 0)
				memo[i] = min(memo[i], memo[i/3] + 1);
		}
		
		System.out.println(memo[num]);
		
		sc.close();
		return;
	}
}

 

2.2 Top-Down

import java.util.*;

public class Main {

    static int[] memo = new int[1000001];

    public static int makeOne(int n){
        if(n <= 1)
            return 0;
        if(memo[n] > 0)
            return memo[n];

        int min = makeOne(n-1);
        if(n % 3 == 0)
            if(min > makeOne(n/3))
                min = makeOne(n/3);
        if(n % 2 == 0)
            if(min > makeOne(n/2))
                min = makeOne(n/2);
        memo[n] = min + 1;
        return memo[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        memo[0] = memo[1] = 0;

        int N = sc.nextInt();
        System.out.println(makeOne(N));
        sc.close();
    }
}