백준 1463번: 1로 만들기 [DP] - Java

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

Top - Down 방식 (재귀)

 

N의 최솟값은 N-1 혹은 N/2 혹은 N/3 된 것의 최솟값 + 1이다.

dp[]에 저장해두고 매번 연산하지않고 저장된 값이 있으면 불러와서 사용한다.

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

public class Main {

	public static int N;
	public static int[] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		dp = new int[N+1];
		
		//solve

		System.out.println(solve(N));
	}
	
	public static int solve(int num) {
		if(num==1) {
			return 0;
		}
		if(dp[num]>0) {
			return dp[num];
		}
		dp[num] = solve(num-1)+1;
		
		if(num%3==0) {
			dp[num] = Math.min(solve(num/3)+1,dp[num]);
		}
		if(num%2==0) {
			dp[num] = Math.min(solve(num/2)+1,dp[num]);
		}
		
		return dp[num];
		
	}

}

 

 

Bottom - Up 방식

반복문으로 0~N까지 각각 최솟값을 구해서 dp[]에 저장한다.

package algorithm.boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Fun12852 {

	public static int[] dp;
	public static ArrayList<Integer> list = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {


		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		dp = new int[n+1];

		dp[0] = dp[1] = 0;
		for (int i = 2; i <= n; i++) {
			
			dp[i]= dp[i-1]+1;
			if(i%3==0) {
				dp[i]=Math.min(dp[i], dp[i/3]+1);
			}
			if(i%2==0) {
				dp[i]=Math.min(dp[i], dp[i/2]+1);
			}
			
		}
		
		System.out.println(dp[n]);
		
	}

}