[Baekjoon] 백준 1463번. 1로 만들기- Java

 

점화식 세우는데 익숙하지 않아서 조금 헤맨 문제

 

N 이라는 수가 주어졌을 때 N을 1로 만드는 최소의 방법은

 

1. N-1 을 1로 만드는 최소 횟수 + 1

2. N/3 을 1로 만드는 최소 횟수 + 1

3. N/2 을 1로 만드는 최수 횟수 +1

 

중에 최소값 입니다. 

 

즉 d[N] = Min ( d[N-1] , d[N/3] d[N/2] ) + 1 이 됩니다. 

 

 

Top - Down 방법

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int d[];
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int target = scan.nextInt();
	
		d = new int[target+1];
		Arrays.fill(d, -1);
		d[0] = 0; d[1] = 0;
		topdown(target);
		
		System.out.println(d[target]);
		
	}
	
	public static int topdown( int n) {
		if(d[n] < 0) {
			int min = Integer.MAX_VALUE;
			min = Math.min(min, topdown(n-1));
			
			if(n%3 == 0)
				min = Math.min(min,  topdown(n/3));
			if(n%2 == 0)
				min = Math.min(min,  topdown(n/2));
			
			d[n] = min+1;
			
			return d[n];
		}
		
		else {
			return d[n];
		}
		
	}

}

 

Bottom - Up 방법

import java.util.Scanner;

public class Main {
	static int min;
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int target = scan.nextInt();
	
		int d[] = new int[target+1];
		d[0] = 0; d[1] = 0;
		
		for(int i = 2; i<=target; i++) {
			d[i] = d[i-1]+1;
			
			if(i%3 == 0) {
				d[i] = Math.min(d[i/3]+1, d[i]);
				
			}
			if(i%2 == 0) {
				d[i] = Math.min(d[i/2]+1, d[i]);
			}
		}
		
		System.out.println(d[target]);
	}
	

}