[백준][1463번] 1로 만들기

문제 URL

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

나의 풀이

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

public class Main {
    public static final int MAX = 1000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //mem[n] = N을 1로 만드는 최소 연산횟수
        int[] mem = new int[MAX+1];
        mem[2] = mem[3] = 1;

        //mem[n] = 1+MIN(mem[N/2],mem[N/3],mem[N-1])
        for(int i=4; i<=n; i++){
          // -1로 뻇을때
            int min = mem[i-1];
            if((i%3) == 0) // 3으로 나눌때
                min = Math.min(min, mem[i/3]);
            if((i%2) == 0) // 2로 나눌때
                min = Math.min(min, mem[i/2]);
            mem[i] = min + 1;
        }
        System.out.println(mem[n]);
    }
}

다른 풀이(Top-bottom)

import java.util.*;

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

다른 풀이(bottom-top)

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]);
    }
}

느낀점

동적계획법 을 이용한 문제다. mem[n] = 1+MIN(mem[N/2],mem[N/3],mem[N-1])

• 탐욕법이 아닌이유 3으로 나누는 것이 수를 빠르게 작게만든다. 따라서 우선순위를 3으로 나누고, 2로 나누고, 1을 빼는것으로 N을 1로 만드는 것을 생각해볼수있다. 하지만, 탐욕법을 이용하면 10->5->4->2->1 총 4번이 걸리는데 10->5->3->1 이라는 3번걸리는 반례가 존재 하기때문이다.

• 시간복잡도 함수 호출 횟수 * 함수의 시간복잡도 = 문제의 개수 * 문제 1개푸는데 필요한 시간복잡도 = N * O(1) = O(N)