[알고리즘][DP][1463] 1로 만들기

[알고리즘][DP][1463] 1로 만들기 

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

[풀이]

• 본격적인 DP문제
• 처음 풀어서 쉽지 않았다.
• 최소값을 고려해야만 문제를 풀 수 있다. (이것 때문에 굉장히 머리 아팠다)
• 10 = 9 -> 3 -> 1 (3회) 가 10 = 5 -> 4 -> 2 -> 1 (4회) 보다 효율적이다.
• EX > num=10 일 때, 
• d[10] = DP(9)+1 => DP(3)+1 +1 => DP(1)+1 +1 +1  
• temp = DP(5)+1 => DP(4)+1 +1 => DP(2)+1 +1 +1 => DP(1) +1 +1 +1 +1 
• temp 가 작을 경우 d[10]에 temp를 넣어준다. 
• 이런 식으로 최소값을 얻는다.

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class q_1463 {
    public static int[] d;
    
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        d = new int[num+1];
        System.out.println(DP(num));
    }
        
    public static int DP(int num) {
        if(num==1) {
            return 0;
        }
        if(d[num]>0) {
            return d[num];
        }
        d[num] = DP(num-1)+1;
        if(num%2 == 0) {
            int tmp = DP(num/2)+1;
            if (d[num] > tmp) {
                d[num] = tmp;
            }
        }
        if(num%3 == 0) {
            int tmp = DP(num/3)+1;
            if (d[num] >tmp) {
                d[num] = tmp;
            }
        }
        return d[num];
    }
 
 
}
 

1. 쉽지 않지만 다시 풀어보고 숙지하기!
2. 어려워도 포기하지 않고 계속 풀자!