[백준 1463]1로 만들기 (Java) - 다이나믹프로그래밍

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

1로 만들기

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[]D = new int[N+1]; // 1부터 시작

        // 아는 수는 먼저 채워줌 : 1을 1로 만드는 연산개수는 0
        D[1] = 0;

        for(int i=2; i<N+1; i++){
            D[i] = D[i-1] + 1; // 1을 빼는 방법
            if (i%2 == 0){ // 2로 나누는 방법
                D[i] = Math.min(D[i], D[i/2] + 1);
            }
            if (i%3 == 0){ // 3으로 나누는 방법
                D[i] = Math.min(D[i], D[i/3] + 1);
            }
        }

        System.out.println(D[N]);
    }
}

• DP를 활용한 문제
• 이미 아는 수를 미리 입력해놓은 후 -> 원하는 값이 나오도록 top down 방식을 채택했다
• 일차원 배열D를 선언해주고, 1부터 시작하기 때문에 N+1크기로 선언해주었다.
• 연산은 다음과 같은 세가지만 수행할 수 있다.
  • 1을 뺀다
  • X가 2로 나누어떨어지면 2로 나눈다.
  • X가 3으로 나누어떨어지면 3으로 나눈다.
• 일단 D[1] = 0이다. 1을 1로 만들 수 있는 최소 연산횟수는 0개이기 때문이다.
• D[i]은 i를 1로 만들기 위한 최소연산횟수 이다.
• 일반 점화식
  • 만약 i가 2로 나누어떨어질 경우, D[i-1] + 1과 D[i / 2] + 1을 비교해서 작은 값으로 업데이트 한다.
  • 만약 i가 3로 나누어떨어질 경우, D[i-1] + 1과 D[i / 3] + 1을 비교해서 작은 값으로 업데이트 한다.
• 위 연산을 i가 2~N이 될때까지 반복수행하고 D[N]을 출력한다.