[JAVA] BOJ 1463 1로 만들기

생각보다 간단하게 풀 수 있는 문제였는데 정답 비율이 낮아서 놀랐다. 동적 계획법 문제이다 보니 이 역시도 메모이제이션과 점화식만 찾아내면 문제를 풀 수 있다. 이 문제는 연산을 사용하는 횟수의 최솟값을 출력하는 문제이다 보니 메모이제이션 해야 하는 값은 주어진 N을 1로 만드는데 까지 드는 연산 횟수의 최솟값이다. N이 2로 나누어지는지 3으로 나누어지는지에 따라 다른 케이스로 나뉘며, 각 케이스마다 N을 1로 빼는 케이스가 더해져 최솟값을 비교해야 한다.

 

예제를 보면, 10을 입력했을 때 10은 2로 나눠지기 때문에 F(10) = Math.min(F(10/2),F(10-1)) + 1으로 구할 수 있다. 한번 다음 단계로 갈 때마다 횟수를 추가해줘야 하기 때문에 +1을 한 것이다. 위의 식은 다시 F(5)와 F(9)의 경우로 나누어지는데 5는 2와 3으로 나누어지지 않기 때문에 F(5) = F(5-1) +1 이 되고 F(9)는 3으로 나누어 떨어지기 때문에 F(9) = Math.max(F(3), F(8)) + 1 이 된다. 매번 계산된 F(N)의 값은 DP 배열을 만들어 DP[N]에 할당하여 메모이제이션을 한다.

 

코드는 다음과 같다.

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


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

 

문제에서 주어지는 N의 크기는 1부터 1,000,000까지의 수이기 때문에 DP 배열은 그에 맞게 사이즈를 지정해주었다. makeone 메서드를 보면, N이 1이 되면 0을 return 하고, DP[N] 에 방문하지 않았다면 (DP[N]==0) 이라면 N이 2 혹은 3으로 나누어지는지에 따라 조건문을 나누어 재귀 함수를 호출하였다. 만약 N이 3으로 나누어 떨어지면 DP[N]은 makeone 메서드에 (N-1)을 파라미터로 준 리턴 값과 (N/3)을 파라미터로 준 리턴 값을 비교하여 더 작은 값에 1을 더한 값을 할당한다.