[백준: 알고리즘_Java] 1463_1로 만들기

 

<문제>

 

 

---

<풀이>

시간 제한이 0.15초로 너무 짧아서.. 고민하다가 이 문제의 분류가 다이나믹 프로그래밍이라서 구글에 검색을 해보았더니.....

 

다이나믹 프로그래밍(동적 프로그래밍)

: 분할정복 알고리즘처럼 큰 문제를 작은 단위로 나누어 풀면, 작은 문제들이 겹쳐서 비효율적이다.

-> 이렇게 겹치는 작은 문제들을 따로 저장해 두었다가 다음번 문제를 풀 때 바로 적용. --> 효율적

피보나치 수열을 구하는 과정이 대표적인 예시. (재귀함수 호출 X)

 

사용 조건 :

1. 최적 부분 구조 (Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

분류:

1. top-down(탑다운, 하향식) : 재귀함수 사용
2. bottom-up(보텀업, 상향식) : 반복문 사용

 보텀업이 더 빠름.

 

 

import java.io.*;
public class MakeOne {

    public static int[] mo = new int[(int) (Math.pow(10, 6)+1)];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력받은 수
        int num = Integer.parseInt(br.readLine());

        //2 1  3 1  4 2 1  4 3 1  5 4 3 1  6 2 1  7 6 3 1  8 4 2 1  12 4 2 1
        //mo[2] = 1, mo[3] = 1, m[4] =min(1+mo[2], 1 + mo[3]), 5 = 1+mo[4], 6 =min(1+ mo[2], 1+mo[5]), 7 = 1+ mo[6],
        //mo[8] = min(1+mo[4], 1+mo[7]), mo[9] = min(1+mo[3], 1+mo[8]), mo[10] = min(1+mo[5], 1+mo[9])

        //2,3의 배수 x -> 1+mo[n-1]
        //2,3의 배수 -> 1+min(mo[n/3], mo[n/2], mo[n-1])
        //(2의 배수가 아닌)3의 배수 - > 1+min(mo[n/3], mo[n-1])
        //(3의 배수가 아닌)2의 배수 -> 1+min(mo[n/2], mo[n-1])


        mo[1] = 0;
        mo[2] = 1;
        mo[3] = 1;

        if(num > 3) {
            for(int i = 4; i <= num; i++) {
                if(i%6 ==0) {
                    mo[i] = 1+ Math.min(Math.min(mo[i/3], mo[i/2]), mo[i-1]);
                } else if(i%3 ==0) {
                    mo[i] = 1+ Math.min(mo[i/3], mo[i-1]);
                } else if(i%2==0) {
                    mo[i] = 1+ Math.min(mo[i/2], mo[i-1]);
                } else {
                    mo[i] = 1 + mo[i-1];
                }
            }
        }

        bw.write(String.valueOf(mo[num]));
        bw.close();


    }
}

---

<결과>

런타임 에러는.. 처음에 계산한 값 저장할 배열 크기를 잘못 정해서..

틀린 건.... 6의 배수일 때를 그냥 3의 배수일때와 똑같이 생각해서..