1로 만들기

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

1463번: 1로 만들기

 

1. 3으로 나누어 떨어지면 3으로 나눈다. 

2. 2로 나누어 떨어지면 2로 나눈다. 

3. 1을 뺀다. 

 

최소 연산으로 N을 1로 만드는 횟수를 구하는 문제

 

Dynamic Programming 배열 D[] 라고 가정하면,

D[n] 은 n을 1로 만드는 최소 횟수를 저장한다.

D[1] = 0 

D[2] = 1;

D[3] = 1;

D[4] = 4 -> 2 -> 1 , 4 -> 3 -> 1 두가지 방법으로 1로 만든다. 

 

n이  3으로 나누어 떨어졌을 때, 3으로 나누는 경우

 -> D[n/3] + 1 

 

n 이 2로 나누어 떨어졌을 때, 2로 나누는 경우

-> D[n/2] + 1

 

n에서 1을 빼는 경우 

D[i-1] + 1 

 

세개 중 최솟값으로 넣는다. 

 

Bottom Up 방법을 사용해서

작은 문제부터 n (큰 문제) 의 해답을 구한다. 

import java.util.*;

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