백준 동적계획법 - 1463번 : 1로 만들기

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

1463번: 1로 만들기

---

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int[] memo = new int[1000001];
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		memo[1] = 0;
		for(int i = 2; i<=n; i++) {
			memo[i] = memo[i-1]+1;
			if(i%2==0) {
				memo[i] = Math.min(memo[i], memo[i/2]+1);
			}
			if(i%3==0) {
				memo[i] = Math.min(memo[i], memo[i/3]+1);
			}
		}
		bw.write(memo[n]+"");
		bw.close();
	}
}