백준 1463 1로만들기

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

DP는 영잼병이라 계속 꺼렷는데.. 계속 꺼리니까.. 안하게되서 이참에 정복해보기..

실버3부터.. ㅎㅎ

메인로직

1. 메모이제이션을 이용하자

해당 메모이제이션을 이용한 코드는 다음과 같다

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

public class 일로만들기 {

	static int[] dp;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int k = Integer.parseInt(br.readLine());
		
		dp = new int[k+1];
		
		
		
		find(k,0);
		
		System.out.println(dp[1]);
	}
	public static void find(int k, int cur) {
		// TODO Auto-generated method stub
		dp[k] = cur;
		

		
		if(k%3==0 && k/3!=0) {
			if(dp[k/3]>cur+1 || dp[k/3]==0) {
				find(k/3,cur+1);
			}
		}
		
		if(k%2==0 && k/2!=0) {
			if(dp[k/2]>cur+1 || dp[k/2]==0) {
				find(k/2,cur+1);
			}
		}
		
		if(k>1) {
			if(dp[k-1]>cur+1 || dp[k-1]==0) {
				find(k-1,cur+1);
			}
		}
		
	}

}

흠...

메모이제이션 문제는 이제 괜찮은데 .. 점화식 세우는 부분이 너무어렵긴하다 ㅠㅠ

많이풀어봐야겠다..