[백준][BOJ-1463][자바] 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

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

public class Main {
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[1000001];
		dp[2] = 1;
		dp[3] = 1;
		
		for(int i=4; i<=n; i++) {
			dp[i] = dp[i-1] +1;
			if(i % 3 ==0) {
				if( dp[i / 3] < dp[i]) {
					dp[i] = dp[i / 3] +1;
				}
			}
			
			if( i % 2 == 0) {
				if( dp[i/2] <dp[i]) {
					dp[i] = dp[i/2]+1;
				}
			}
		}
		
		System.out.println(dp[n]);
	}
}

정리

먼저 메모리제이션으로 풀어봤습니다. 문제에 주어진 대로 연산을 사용하는 횟수의 최솟값을 구하기 때문에 최대한 -1을 적게 하면 좋습니다.

따라서 2와 3은 최소 1번 수행에 4부터 3번 조건으로 dp[i-1] +1의 최솟값을 가지고 시작합니다.

하지만 4는 2로 나누어 지고, 그러면 2로 나눈 dp[2] 보다 한 번 더 실행하게 됩니다. 따라서 dp[4] = 2;

이번에는 5를 봅시다. 3번 조건에 의해 4의 최소 연산의 +1이을 최소값을 가지고 되고 조건 1과 조건 2가 맞지 않기 때문에 5는 3번의 연산이 이루어집니다. dp[5] = 3;

마지막으로 6을 보자 3번 조건에 의해 5보다 +1한 값인 dp[6] = 4 조건으로 시작합니다. 1번을 만족하고 dp[2]와 비교했을 때 dp[2]가 값이 더 작다 따라서 dp[2] +1; 을 해주면 dp[6] = 2가 됩니다.

위를 n번이하 까지 반복하면 각 숫자는 최소 연산을 가지게 됩니다.

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

public class Main {
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		dfs(0,Integer.parseInt(br.readLine()));
		
		System.out.println(min);
	}
	
	public static void dfs(int cnt, int num) {
		if(min < cnt) return;
		if(num == 0) {
			min = Math.min(min, cnt-1);
			return;
		}
		
		if(num%3 == 0) dfs(cnt+1, num/3);
		if(num%2 == 0) dfs(cnt+1, num/2);
		dfs(cnt+1, num-1);
	}
}

다음은 재귀형태로 풀어봤습니다.

먼저 if문으로 3이나 2로 나누어지면 재귀를 돌려주고 -1은 무조건 재귀를 돌게 했습니다.

여기서 num이 0이라는 말은 연산이 끝났다는 말이고 최소 연산을 비교해서 저장합니다.

가지치기로 최소 연산 횟수보다 연산 횟수가 많아진다면 더 이상 연산할 필요가 없기 때문에 return 해주었습니다.