6주차 : 다이나믹 프로그래밍 문제 1

✔ BOJ_1463

다이나믹 프로그래밍의 정의를 잘 이해 못하겠어서 바로 문제를 풀기보단 인터넷에 올라와 있는 풀이를 기반으로 다이나믹 프로그래밍을 이해하고자 했습니다.

참조

d[n]에 n을 1로 만들기 위한 최소 개수를 저장합니다. 재귀함수(top dow)이나 반복문(bottom up)을 사용하여 구할 수 있어 두 가지 다 따라해(?) 보았습니다.

d[0]과 d[1]은 3으로 나누거나 2로 나누거나 1을 빼서 1을 만들어낼 수 없으므로 d[0]=d[1]=0이 됩니다.

해당 문제에서 가능한 연산은 총 세 개입니다.
첫번째 1을 빼는 것은, d[i] = d[i-1]+1이되고 (i-1이 1이면 i는 i-1에 -1을 해주어야할 것이빈다. 따라서 d[i-1] 연산횟수에 -1 을 한 번 더 해주는 연산횟수를 추가하여 d[i] = d[i-1]+1이 되는 것 입니다.)

두 번째 2를 나누는 것은, d[i] =d[i/2]+1이 됩니다.
마찬가지로 3을 나누는 것은 d[i] = d[i/3]+1이 됩니다.

따라서 bottom up 코드는 다음과 같아집니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class BOJ_1463{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        int d[] = new int[n+1];
        d[0] = 0;
        d[1] = 1;
        for(int i=2;i<=n;i++){
        	d[i] = d[i-1] +1;
            // 더 작은 것을 넣기
            if(i%2==0) d[i] =Math.min(d[i], d[i/2]+1);
            if(i%3==0) d[i] = Math.min(d[i], d[i/3]+1);
            }
         System.out.println(d[n]);
         }}

해당 내용을 top down으로 짠 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463{
	public static int d[];
    public static void main(String[] args) throws IOException{
    	BUfferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        d = new int[n+1] ;
        System.out.println(calculate(n));}
  [
  public static int calculate(int n){
  	if(n==1) return 0;
    if(d[n] >0 ) return d[n];
    d[n] = calculate(n-1)+1;
    if(n%3==0){
    	d[n] = Math.min(d[n], calculate(n/3)+1);}
   	if(n%2==0){
    	d[n] = Math.min(d[n], calculate(n/2)+1);}
    return d[n];}}