[다이나믹 프로그래밍] 문제 이름 : 1로 만들기

문제 설명

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

1. X가 5로 나누어떨어지면, 5로 나눔

2. X가 2로 나누어떨어지면, 2로 나눔

3. X가 3으로 나누어떨어지면, 3으로 나눔

4. X에서 1을 뺌

 

정수 X가 주어졌을 때, 위의 연산 4개를 적절히 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 구하시오.

---

사용 개념

다이나믹 프로그래밍, 보텀업 방식 

---

문제 해결 아이디어

 

모든 연산 가능 경우에 대해 생각해봐야 할 것 같은데 너무 많은 것 아니야..? → 맞아! 경우의 수로 모든 경우에 대해 봐야되는거 맞는데 다이나믹 프로그래밍을 사용해서 빠르게 구하는거지! 어차피 최소 연산 횟수 구하는 것이니까! 

1. 함수 호출 과정 도식화하기 

 

주어진 값이 6일 때 함수가 호출되는 과정(= 모든 경우의 수)

→ 모든 경우의 수에 대해 고려할 때 동일한 함수들이 여러 번 호출됨을 알 수 있음

→ 이때 동일한 함수에서 구하는 값들은 모두 동일해야 하므로 다이나믹 프로그래밍 적용 가능 

 

** 다이나믹 프로그래밍을 사용하기 위한 조건

https://fordevelop.tistory.com/53#다이나믹-프로그래밍을-사용하기-위한-조건

 

2. 점화식 표현 

점화식 표현

→ aᵢ : i 값을 1로 만들기 위해 필요한 최소 연산 횟수 

3. 점화식을 바탕으로 보텀업(Bottom-Up) 다이나믹 프로그래밍 코드 작성

---

코드

import java.util.Scanner;

public class Main {
	public static int[] result = new int[30001];	// 배열의 원소 값 : 해당 값을 1로 만들기 위해 필요한 연산 횟수의 최소값, 한 번 계산된 결과를 배열에 저장해둠 
	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		int val = kbd.nextInt();	// 최대 : 30,000 
		
        // 다이나믹 프로그래밍 진행(보텀업)
		for(int i = 2; i <= val; i++) {
			// 연산1. 현재의 수 - 1
			result[i] = result[i-1] + 1;
			
			// 연산2. 현재의 수가 2로 나누어 떨어지는 경우
			if (i % 2 == 0)
				result[i] = Math.min(result[i], result[i/2] + 1);
			
			// 연산3. 현재의 수가 3으로 나누어 떨어지는 경우
			if (i % 3 == 0)
				result[i] = Math.min(result[i], result[i/3] + 1);
			
			// 연산4. 현재의 수가 5로 나누어 떨어지는 경우 
			if (i % 5 == 0)
				result[i] = Math.min(result[i], result[i/5] + 1);
		}
		
		
		// 연산 하는 횟수의 최솟값 구하기 
		System.out.println(result[val]);
	}

}

 

→ 구하는 것 : 사용자가 입력한 값을 1로 만들기 위해 필요한 연산 횟수의 최소값 (= result[x] 값)

→ 배열의 원소 값 : 해당 값을 1로 만들기 위해 필요한 연산 횟수의 최소값

→ 보텀업 방식으로 작은 값부터 차례대로 연산 횟수의 최소값을 구함