백준 1463

문제

---

dp[N] : N에서 1을 만드는 최소 연산 횟수를 저장한다

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

문제에 따르면 매 번 위의 연산 중 하나를 선택해야 한다.
i번째 연산을 할 차례(이 때 숫자는 A)라고 가정한다. 3개의 연산 중 무엇을 선택하던 연산 횟수는 +1 추가된다.

문제는 i+1 번째부터 시행할 연산 횟수이다.
즉,

A/3, A/2, A-1 중 어느 숫자를 가장 적은 연산으로 1로 만들 수 있는가의 문제

그런데 만약 2 또는 3으로 나누어 떨어지지 않는다면 그 경우는 제외해도 됨.

---

Code

package test;

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

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

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

---

참고 : https://st-lab.tistory.com/133