[JAVA] 백준 1463번 - 1로 만들기

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	static int dp[] = new int[1000001];
	
	public static int f(int x) {
		if(dp[x] != 0) return dp[x];
		else {
			if(x % 6 == 0) {
				if(dp[x/3] < dp[x/2]) {
					return f(x/3)+1;
				}else {
					return f(x/2)+1;
				}
			}else if(x % 3 == 0){
				if(dp[x/3] < dp[x-1]) {
					return f(x/3)+1;
				}else {
					return f(x-1)+1;
				}
			}else if(x % 2 == 0){
				if(dp[x/2] < dp[x-1]) {
					return f(x/2)+1;
				}else {
					return f(x-1)+1;
				}
			}else {
				return f(x-1)+1;
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;

		for (int i = 4; i <= N; i++) {
			dp[i] = f(i);
		}
		
		System.out.println(dp[N]);
		
		/*
		for (int i = 1; i <= N; i++) {
			System.out.println(i+" : "+dp[i]);
		}
		 */
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

x가 6으로 나눠질 때 반례가 나올 수 있기 때문에 (x % 6 == 0)인 경우도 고려해야합니다.

 

 

 

🔗 링크

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

1463번: 1로 만들기