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

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

1463번: 1로 만들기

 

 

[시행 착오]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        if (N <= 3) {
            System.out.println(1);
        } else if (N % 3 == 0) {
            System.out.println(N / 3);
        } else if (N % 3 == 1 && N % 2 == 0) {
            System.out.println((N / 3));
        } else if (N % 3 == 1){
            System.out.println((N / 3) + 1);
        } else if (N % 2 == 0) {
            System.out.println(N / 2);
        } else {
            System.out.println((N / 3) + 1);
        }
    }
}

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[N + 1];
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 뺀값
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 1을 뺀값과 2로 나눈값준 최솟값
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1); // (1을 뺀 값과 2로 나눈 값중 최솟값) 과 3으로 나눈값중 최솟값
            }
        }
        System.out.println(dp[N]);
    }
}

 

[설명]

이 문제는 DP 문제이다.

DP 문제는 3가지 단계를 생가해야 된다고 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

 

1. 테이블 정의

dp[i] = i를 1로 만들때 연산을 해야하는 횟수의 최솟값

 

2. 점화식 찾기

dp[12] 을 예로들자면

3으로 나누거나 (dp[12] = dp[4] + 1) = (dp[i] = dp[i/3] + 1)

2로 나누거나 (dp[12] = dp[6] + 1) = (dp[i] = dp[i/2] + 1)

1을 빼거나 (dp[12] = dp[11] + 1) = dp[i] = dp[i-1] + 1)

-> dp[12] = min(dp[4] + 1, dp[6] + 1, dp[11] + 1)

-> dp[i] = min(dp[i/3] + 1, dp[i/2] + 1, dp[i-1] + 1)

 

3. 초기값 정하기

dp[0] = dp[1] = 0

 

사실 이 모든 아이디어는 내 아이디어가 아니다. dp 문제는 가장 자신없어 하는 분야이기도하고 점화식을 계산하는법을 도저히 떠올릴수가 없다ㅠㅠ. 그래서 어느 한 블로그를 참고했다. 내가 푼 문제라고 볼 수 없다.

 

참고 : 

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java-%EC%9E%90%EB%B0%94