[200316/D-4] 백준 알고리즘 공부

푼 문제 :  1463

전체 비율 :  / 155 (약 %) 

공부 시간 : 

 

어떤 방식으로 풀어야되는지 아애 감이 안왔다.  

생각 끝에 일단 이 부분은 몇 개 힌트를 찾아서 풀어보면서 내 방식을 찾기로 했다.

 

다이나믹 프로그래밍 (DP) : 하나의 문제는 단 한 번만 풀도록 하는 알고리즘. 비효율적인 알고리즘 개선. 

다이나믹 프로그래밍을 하는 방식은 1. Top-Down 2. Bottom-up 이렇게 두 가지 존재한다.

1. Top-up : 재귀 함수 이용

2. Bottom-up : 반복문 이용

공통적으로는 계산의 중복을 줄이기 위해서 배열을 생성해서 계산 결과를 저장해놓고 사용한다.  작은 문제들 >> 큰 문제로 해결하는 방식.

 

 

1463 

1로 만들기

 

Bottom-up (Git)

import java.util.Scanner;

public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        
        int dp[] = new int[num+1];
        
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= num; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);       	
        }
        
        System.out.println(dp[num]);

    }
    

}

Top-up

import java.io.IOException;
import java.util.Scanner;

public class Main{
    
    public static int dp[];
    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        dp = new int[num+1];
        System.out.println(calculate(num));
    }

    public static int calculate(int num){
        if (num == 1) return 0;
        if (dp[num] > 0){
            return dp[num];
        }
        
        dp[num] = calculate(num-1) + 1;
        if (num%3 == 0) {
            dp[num] = Math.min(dp[num],calculate(num/3) +1);
        }
        if (num%2 == 0) {
            dp[num] = Math.min(dp[num],calculate(num/2) +1);
        }
        return dp[num];
    }
}

이 방식으로 생각했었는데 처참하게 실패.

실패 원인은 일단 배열을 사용 하겠다고 생각 못 했던 것이고 하나 하나 또 계산 하려고 했다는 점.