[백준] 1463번 - 1로 만들기 (Java)

 

 

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

1463번: 1로 만들기

 

<문제 분석>

DP(Dynamic Programming) 문제 푸는 공식 3단계

1) DP 테이블 정의

2) 점화식 찾기

3) 초기값 정하기

 

1. 테이블 정의

DP[i] = 정수 i를 1로 만들때까지 걸리는 연산 횟수의 최소값

 

2. 점화식 찾기

DP[12]의 경우

a. 3으로 나눌 경우

  -> DP[12] = DP[4] + 1

  -> DP[x] = DP[x/3] + 1

b. 2로 나눌 경우

  -> DP[12] = DP[6] + 1

  -> DP[x] = DP[x/2] + 1

c. 1을 뺄경우

  -> DP[12] = DP[11] + 1

  -> DP[x] = DP[x-1] + 1

경우의 수 중에서 최소값을 구해야 하기 때문에 점화식은 아래와 같다.

DP[x] = min(3으로 나눌 경우, 2로 나눌 경우, 1을 뺄 경우)

 

3. 초기값 정의하기

DP[0] = DP[1] = 0

 

※ 놓친 부분

1. 큰 값으로 나눈다고 항상 최소값이 도출되는 것이 아닌데 그것을 간과함.

  - 3과 2, 둘 다 나눠지는 수의 경우 두 개 중 더 적은 수가 어떤 것인지 모르기 때문에 미리 비교를 해야한다.

2. 메모이제이션을 사용해야 하는데 사용법을 확실하게 몰랐음.

  - dp[i]에 값이 얿을 경우에만 재귀 호출을 하고, 있으면 그 값을 바로 리턴함.

 

<코드 구현>

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	int N;
    int dp[] = new int[1000000+1];

	void InputData(){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		sc.close();
	}

    public int min = Integer.MAX_VALUE;
    public int dfs(int x) {
        if (dp[x] == -1) { // dp 테이블이 비었을 경우만 재귀호출함
            // 6으로 나눠지는 경우
            // 더 큰수로 나눈다고 항상 작은 건 아니기 때문에 3과 2를 항상 비교해서 작은쪽 선택
            if (x%6 == 0) {
                int min = Math.min(dfs(x/3), dfs(x/2)); // 먼저 3과 2중 작은 쪽 선택
                dp[x] = Math.min(dfs(x-1), min) + 1; // 위의 값과 x-1한 값 중 작은 쪽 선택
            } else if (x%3 == 0) { // 3으로만 나눠지는 수
                dp[x] = Math.min(dfs(x/3), dfs(x-1)) + 1; // x/3 vs x-1 중 작은 수 선택
            } else if (x%2 == 0) {
                dp[x] = Math.min(dfs(x/2), dfs(x-1)) + 1; // x/2 vs x-1 중 작은 수 선택
            } else { // x-1 선택
                dp[x] = dfs(x-1) + 1;
            }
        }
        return dp[x]; // 값이 있으므로 메모이제이션 이용
    }
	public int solve() {
        Arrays.fill(dp, -1);
        dp[0] = dp[1] = 0;
        // 1. 재귀로 풀기
        //return dfs(N);

        // 2. 반복문으로 풀기 
        for (int i=2; i<=N; i++) {
            dp[i] = dp[i-1] + 1; // 1 뺀 값의 dp 테이블 참조
            if (i%2 == 0) { // 1 뺀 값과 2로 나눈 값 중 작은 값 참조
                dp[i] = Math.min(dp[i], dp[i/2] + 1); 
            }
            if (i%3 == 0) { // 위의 결과값과 3으로 나눈 값 중 작은 값 참조
                dp[i] = Math.min(dp[i], dp[i/3] + 1);
            }
        }
        return dp[N];
	}

	public static void main(String[] args){
		int ans = -1;
		Main m = new Main();

		m.InputData(); //	입력 함수
		//	코드를 작성하세요
		ans = m.solve();
		System.out.println(ans); //출력
	}
}

 

<제출 결과>

1. 1시간 타이머를 걸고 풀었으나 시간 안에 완벽하게 구현을 하지 못함.

  - DP의 구현방법과 메모이제이션 사용법에 대한 이해가 완벽하지 않은 것 같음.

2. 참고 : https://st-lab.tistory.com/133