[JAVA] 백준 1463 1로 만들기 [ Dynamic Programming ]

전체 코드

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

public class 백준_1463_1로만들기 {

	static int N, d[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		d = new int[N+1];
		d[0] = 0;
		
		System.out.println(dp(N));
		
	}
	
	private static int dp(int n) {
		if(n==1) // n일땐 바로 리턴
			return 0;
		if(d[n] > 0) // d[n] 에 값이 구해질때까지 재귀
			return d[n];
		d[n] = dp(n-1) +1; // 현재값을 전 값의 +1을 넣어놓고
		if(n%2 == 0) { //N이 2로 나누어떨어지면
			int tmp = dp(n/2) +1; // N을 2로 나눈값에 한번 더 연산했으므로 + 1
			if(d[n] > tmp) // 현재값이 더 크다면 현재 값, 아니라면 위의 tmp값을 넣는다.
				d[n] = tmp;
		}
		if(n%3 == 0) { // 2로 나누어 떨어질 때와 마찬가지로
			int tmp = dp(n/3) + 1; // 3으로 나눈값에 한번 더 연산이므로 +1
			if(d[n] > tmp) // 현재값이 더 크다면 현재 값, 아니라면 위의 tmp값을 넣는다.
				d[n] = tmp;
		}
		return d[n];
	}

}

 

문제 핵심 코드

private static int dp(int n) {
	if(n==1) // n일땐 바로 리턴
		return 0;
	if(d[n] > 0) // d[n] 에 값이 구해질때까지 재귀
		return d[n];
	d[n] = dp(n-1) +1; // 현재값을 전 값의 +1을 넣어놓고
	if(n%2 == 0) { //N이 2로 나누어떨어지면
		int tmp = dp(n/2) +1; // N을 2로 나눈값에 한번 더 연산했으므로 + 1
		if(d[n] > tmp) // 현재값이 더 크다면 현재 값, 아니라면 위의 tmp값을 넣는다.
			d[n] = tmp;
	}
	if(n%3 == 0) { // 2로 나누어 떨어질 때와 마찬가지로
		int tmp = dp(n/3) + 1; // 3으로 나눈값에 한번 더 연산이므로 +1
		if(d[n] > tmp) // 현재값이 더 크다면 현재 값, 아니라면 위의 tmp값을 넣는다.
			d[n] = tmp;
	}
	return d[n];
}

 

값들을 누적해가며, 원하는 값이 나올 때 출력하는 방법이었다. DP이지만, 기억 연산법이라는 말이 더 와닿는 문제였다.