[백준] boj 1436 java "1로 만들기" (dp, 다이나믹 프로그래밍)

1로 만들기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.15 초 (하단 참고)

128 MB

185661

59776

37999

31.960%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

 

---

문제해결 접근

dp 문제는, 사용될 거 같은 이전의 계산 값들을 저장해서 꺼내 사용하는 것 = 메모이제이션

 

1. Integer 배열에 초기값들을 넣어준다.

2. 숫자 n의 1로 가는 최소값은 dp_value(n)의 값이다.

3. dp[n] 값은 n 의 최솟 값이다

4. dp[n] 값이 null이라면, 이전의 연산이 가능한 값 + 1 = dp[n] 이다.

5. 연산이 가능한 경우의 수는 3가지 n/3, n/2, n-1 이다.

6. 무조건 큰수로 나누는 것이 최솟값이 되지는 않느다 (ex 5=3, 6=2)

7. 따라서 연산가능한 경우의 수들의 dp[n/3] dp[n/2] dp[n-1] 값들의 최솟값을 이용해야한다.

package solved.Class;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeSet;


public class Main {
    //int는 0초기화 , Integer = null
    static Integer dp[]= new Integer[1000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;


        int n = Integer.parseInt(br.readLine());

        System.out.println(dp_value(n));

    }

    // f(n) = 1+( f(n/3) || f(n/2) f(n-1))
    //각각 연산 가능한 최솟값을 비교하는 이유 -> 반레: 30 5=3 / 6 =2

    public static int dp_value(int n){

        if(dp[n]==null) {
            if(n%6==0)
                dp[n] = 1+Math.min(dp_value(n/3),Math.min(dp_value(n/2),dp_value(n-1)));
            else if (n % 3 == 0)
                dp[n] = 1+Math.min(dp_value(n/3),dp_value(n-1));
            else if (n % 2 == 0)
                dp[n] = 1+Math.min(dp_value(n/2),dp_value(n-1));
            else
                dp[n] = 1+dp_value(n-1);
        }

        return dp[n];
    }

}