백준 1463번(DP) : 1로 만들기 (JAVA) 문제 풀이

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

1463번: 1로 만들기

---

 

✏️ 문제

---

 

🔐 문제 해결

다이나믹 프로그래밍은 아래 세가지 순서를 따라서 문제를 풀이합니다.

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 설정

 

1. 테이블 정의하기

테이블의 값은 당연히 i의 최소 연산 횟수가 되겠습니다.

 

2. 점화식 찾기

i를 계산하는 방법은 총 3가지가 있습니다.

1. 2로 나눈 나머지가 0일 경우, 2로 나눈다.
2. 3으로 나눈 나머지가 0일 경우, 3으로 나눈다.
3. 1을 뺀다.

i의 최소 연산 횟수를 저장하는 배열을 dp라고 정의할 때, dp[i]의 값은 아래와 같습니다.

dp[i] = Math.min(dp[i-1] + 1, dp[i/2] + 1, dp[i/3] + 1);

 

 

3. 초기값 설정

초기값은 1부터 N까지의 연산을 진행할 것이기 때문에 아래와 같이 설정합니다.

dp[1] = 0;

 

---

 

🗝 전체 코드

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] dp = new int[N+1];

        dp[1] = 0;

        for(int i=2; i<= N; i++) {
            dp[i] = dp[i-1] + 1;
            if(i % 2 == 0){
                dp[i] = Math.min(dp[i], dp[i/2] + 1);
            }
            if(i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i/3] + 1);
            }
        }

        System.out.print(dp[N]);
    }
}