1. Problem 📃

[ 1로 만들기 ]

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

[ 문제 ]

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

2. Input ⌨️

[ 입력 ]

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

3. Output 🖨

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

종이에 입력 값 X를 넣어서 하나씩 정리해놓고 보면 그렇게 어렵지 않다.
1. 다이나믹 프로그래밍을 이용한 기록을 담기 위한 전역 배열 변수(dp)를 선언해준다.
2. 입력받을 값을 담을 변수 X를 선언하고 값을 넣어준다.
3. X를 입력받아 dp의 사이즈를 X+1만큼 선언하고 dp[0]과 dp[1]은 실행할 횟수가 없으니 0값을 넣어 초기화 해놓았다.
4. 다이나믹 프로그래밍을 하기위한 메서드(Search)를 선언하고 매개변수는 입력받은 X로 정의해주었다. 우선 1로 만들기 위한 조건에 2나 3으로 나누어 떨어지는 경우에 따른 조건이 존재하므로 최소 공배수 6으로 나누어 떨어졌을 때의 상황을 고려하여 코드를 작성하였다.
만약 찾고자 하는 값 dp[X]의 값이 null값이라면 다음과 조건을 따르도록 한다.

4-1) X가 6으로 나누어 떨어진다면 dp[X]는 세 가지 상황 중 가장 작은 값으로 들어간다. Math.min()을 이용하여 또 그 안에서 Math.min()으로 X를 3으로 나누었을 때와 2로 나누었을 때의 값들을 구하고, 그 중 작은 값을 Search(X-1)을 한 값을 비교하고 결국 이전의 dp[]의 값에 한 번을 더 추가하는 과정이므로 해당 연산에 대한 +1의 값을 넣어준다.

4-2) X가 3으로 나누어 떨이진다면 3으로 나누거나 1을 빼거나 둘 중 하나이므로 Math.min()을 이용하여 Search(X/3)과 Search(X-1)을 한 값들 중 작은 값을 구하고 해당 연산에 대한 +1의 값을 넣어준다.

4-3 X가 2로 나누어 떨어진다며 2로 나누거나 1을 빼거나 둘 중 하나이므로
Math.min()을 이용하여 Search(X/2)와 Search(X-1)을 한 값들 중 작은 값을 구하고 해당 연산에 대한 +1의 값을 넣어준다.

4-4 위에 모든 경우를 제외한다면 1을 빼는 경우 밖에 존재하지 않으므로 Search(X-1)한 값에 해당 연산에 대한 +1의 값을 넣어준다.

그 후 dp[X]값을 반환하여 출력한다.

6. Code 💻

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

public class Main {

	public static Integer[] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int X = Integer.parseInt(br.readLine());
		
		dp = new Integer[X+1];
		dp[0] = dp[1] = 0;
		
		System.out.println(Search(X));
		
	}

	private static int Search(int X) {
		
		if(dp[X] == null) {
			if(X % 6 == 0) {
				dp[X] = Math.min(Math.min(Search(X/3),Search(X/2)), Search(X-1))+1;
			}
			else if(X % 3 == 0) {
				dp[X] = Math.min(Search(X/3), Search(X-1))+1;
			}
			else if(X % 2 == 0) {
				dp[X] = Math.min(Search(X/2), Search(X-1))+1;
			}
			else {
				dp[X] = Search(X-1)+1;
			}
		}
		
		return dp[X];
	}

}

7. Growth 🍄