동적계획법_1463_1로만들기

동적 계획법

주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 큰 문제를 푸는 것
F(N)을 구하기 위해서 풀어야 하는 문제의 개수는 O(N)개 이고, 이 답을 모두 저장할 O(N)의 메모리가 필요하며, 각각의 문제를 푸는 데 걸리는 시간이 O(1)이므로 O(N)개의 문제를 푸는 데 O(N)의 시간이 든다.

분할 정복 VS DP
분할정복과의 차이점은 분할정복은 문제를 분할했을 때 생성되는 부분 문제들 중 겹치는 문제가 발생하지 않는다. 
하지만 DP는 겹치는 문제가 발생하기 때문에 메모이제이션 기법이 필요하다.
EX) 피보나치 -> F(N)[구해야할 문제] = F(N-1) [ 부분 문제 ] + F(N-2) [ 부분 문제 ]

Greedy VS DP
모든 경우를 메모리까지 소비해가며 샅샅이 체크하는 점에서 실행시간이 그리지 알고리즘보다 길지만, 좀 더 폭 넓은 범위에서 근사치가 아닌 정확한 값을 얻을 수 있다.

TopDown(재귀) VS BottomUp(반복문)
탑다운은 가독성이 좋고, 본래의 점화식을 이해하기 쉬운 장점이 있다. 
바틈업은 함수를 별개로 호출하지 않아 시간과 메모리를 소량 더 절약할 수 있는 장점이 있다.

 

 

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

1463번: 1로 만들기

1. 점화식 구성하기 

F(N) -> 정수 N을 1로 만드는 최소의 경우의 수 구하는 함수
min(
    0                N =1
    F(N/3)+1    N이 3배수
    F(N/2)+1    N이 2배수
    F(N-1)+1    나머지
)

+1을 해주는 것은 나누기 혹은 빼기 연산을 한 것 자체가 한 번의 연산을 한 것이기 때문에 카운트 해주는 것이다. 
예를 들어 F(10)이라고 한다면 F(10/2) + 1 = F(5) + 1이 되고 +1은 나누기 2 연산을 1회 카운트 한 것이다.

그렇다면 점화식을 기반으로 해서 DP배열을 구성해보자.
모든 경우의 수를 따지기 전에 모든 정수에 대해서 적용할 수 있는 3가지 연산을 명확히 이해할 필요가 있다. 
1. -1 연산 : 모든 정수에 대해서 가능 
2. /3 연산 : 3의 배수만 가능
3. /2 연산 : 2의 배수만 가능 

즉, 3의 배수도 아니고 2의배수도 아닌 7같은 값은 -1연산을 제외하고 적용할 수 있는 연산이 없다는 것이다. 
따라서 특정 정수 N에 대해서 이 값에 적용할 수 있는 3가지 연산 중 언제나 사용할 수 있는 것이 -1연산이기 때문에 이를 기본 비교 대상으로 삼는다. 

DP배열을 -1로 채우고 아래와 같이 재귀를 구성한다. 

package DynamicProgamming;

import java.util.Arrays;
import java.util.Scanner;

public class _1463_정수1로만들기_탑다운 {
	static int DP[];
	public static void main(String[] args) throws Exception{
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		//1 <= N <= 10^6
		DP = new int[N+1];
		Arrays.fill(DP, -1);
		DP[1] = 0;
		
		int res = Count(N);
		System.out.println(res);
	}

	private static int Count(int N) {
		// TODO Auto-generated method stub
		if(N==1) return 0;
		if(DP[N] != -1) return DP[N];

		int minus = Count(N-1) + 1;
		if(N%3 == 0) minus = Math.min(minus, Count(N/3)+1);
		if(N%2 == 0) minus = Math.min(minus, Count(N/2)+1);
		
		DP[N] = minus;
		return minus;
		
	}
}

 위의 로직을 C로 구현하면, 제출이 되는데, 자바로 구현하니 시간 초과가 난다...... 원인을 아시는 분은 댓글 달아주시면 감사하겠습니다... ㅠ

위의 코드를 바텀업으로 구현하는 방법은 재귀로 구현한 점화식을 반복문으로만 바꿔주면 된다.

package DynamicProgamming;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _1463_정수1로만들기_바텀업 {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		//arr[i]는 i를 1로 만드는데 필요한 최소 연산 횟수를 저장할 배열
		int arr[] = new int[N+1];
		
		arr[1]=0;
		
		//점화식을 사용한 bottomup
		for(int i=2 ; i<=N; i++) {
			arr[i] = arr[i-1] + 1;
			if(i % 2 ==0) arr[i] = Math.min(arr[i], arr[i/2]+1);
			if(i % 3 ==0) arr[i] = Math.min(arr[i], arr[i/3]+1);
			
		}
		System.out.println(arr[N]);
	}

}