백준 1463번

1로 만들기

문제

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

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

입력

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

출력

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

예제

코드

import java.util.*;
import java.io.*;

public class Main {
	public static Integer arr[];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		arr = new Integer[N+1];
		arr[0] = arr[1] = 0;
		
		System.out.println(func(N));
	}
	
	public static int func(int N) {
		if(arr[N] == null) {
			if(N % 6 == 0)
				arr[N] = Math.min(func(N - 1), Math.min(func(N / 3), func(N / 2))) + 1;
			else if(N % 3 == 0)
				arr[N] = Math.min(func(N / 3), func(N - 1)) + 1;
			else if(N % 2 == 0)
				arr[N] = Math.min(func(N / 2), func(N - 1)) + 1;
			else
				arr[N] = func(N - 1) + 1;
		}
		return arr[N];
	}
}

풀이

3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있다. 각 경우를 계산하여 입력값을 1로 만들기 위한 최소값을 구해야 한다.
문제를 해결하면서 착각했던 것이, 단순히 높은 수를 우선으로 나눈다고 그게 최솟값이 아니였다.
작은수로 우선적으로 나눠도 최솟값이 될 수 있다.
각 부분에 재귀호출을 하면서 배열을 최솟값으로 갱신해주어야 한다.

여기서 배열을 Integer 배열로 선언하였는데,
Integer는 int의 래퍼 클래스로서, 기본형을 객체로 다루기 위해 사용하는 클래스이다.
자료형의 경우, null로 초기화가 불가능하다. 반면 래퍼클래스는 null 처리가 가능하고 unboxing하지 않을 시 산술 연산이 불가능하다.

6으로 나누어 떨어지는 경우, 1을 뺀 경우의 재귀, 3으로 나눈 경우의 재귀, 2로 나눈 경우의 재귀 중 최솟값을 구한 것에 +1을 하면 된다.