[백준] 1463_1로만들기 / 동적계획법 DP

 

 

Sliver

 

문제

 

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

 

 

입력

 

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

 

 

출력

 

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

 

 

---

 

풀이

 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N+1];
        for(int i=2; i<=N; i++){
            arr[i] = arr[i-1]+1;
            if(i%2==0)
                arr[i] = Math.min(arr[i], arr[i/2]+1);
            if(i%3==0)
                arr[i] = Math.min(arr[i], arr[i/3]+1);
        }
        System.out.println(arr[N]);
    }
}

 

 

해결 방법

1. 초기화
   • 주어진 정수 N을 입력받은 후 N+1 크기의 배열을 생성한다. 
   • 각 요소에는 index까지 되기 위한 최소 연산 횟수를 저장하게 된다. 
2. 동적 계획법을 이용한 최소 연산 횟수 계산
   • 2부터 N까지 반복하면서, arr[i]를 계산한다.
   • 세 가지 연산 중 i 까지 되기 위한 최소 연산 횟수를 선택하여 업데이트한다. 
     1. arr[i-1] + 1 (1을 뺀 경우 -> 직전 단계에서 1을 더하는 경우)
     2. i가 2로 나누어 떨어지면, arr[i/2] + 1 (2로 나눈 경우 -> 직전 단계에서 2를 곱한 경우)
     3. i가 3으로 나누어 떨어지면, arr[i/3] + 1 (3으로 나눈 경우 -> 직전 단계에서 3을 곱한 경우)
3. 최종 결과 출력:
   • 배열 arr에서 arr[N] 값을  출력한다. 

 

---

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