문제 : 1로 만들기

링크 : BOJ_1463_1로만들기

접근 방식

1보다 큰 정수 N이 주어질 때,

1. N이 3으로 나누어 떨어지면 3으로 나눈다.
2. N이 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다

이 세가지 연산을 사용하여 1을 만드는데, 이를 위해 필요한 연산 횟수의 최솟값을 구해야 한다.

이 문제는 횟수도 횟수지만 시간제한이 괴랄하다. 무려 0.15초.. 역시 DP카테고리에 있기 때문에 DP를 이용하여 풀었다.

DP에 N을 나누는 최소 연산 횟수를 누적시킨다. 예를 들어서, 힌트에 나와있는 10을 통해 최소 연산 횟수를 구한다고 생각해보자.

10 -> 9 -> 3 -> 1 으로 1을 만들 수 있고, 연산 횟수는 3이다.

이를 분해해보자.

1. 3의 경우 3 -> 1 으로 1을 만들 수 있고, 연산 횟수는 1이다.(최소)

2. 9의 경우 9 -> 3 -> 1 으로 1을 만들 수 있고, 연산 횟수는 2이다.(최소)

3. 10의 경우 10->9->3->1 으로 1을 만들 수 있고, 연산 횟수는 3이다. (최소)

큰 문제가 작은 문제로 나뉠 수 있는 것을 확인했다.

그렇다면 이제 각 수에 따른 최소 횟수를 구하는 방법을 체크해야한다.

조건을 따져야 할 것은 위의 세가지 연산에 대한 경우이다.

1. N이 3으로 나누어 떨어질 때, dp배열에 현재 수에서 1을 뺀 수의 연산 횟수와, 현재 수에서 3을 나눈 수의 연산 횟수중 더 작은값을 구한 후 +1을 하여 저장한다. 이때 각각의 연산은 당연히 각각의 수를 1로 만드는 최소 연산 횟수이다.

2. N이 2로 나누어 떨어질 때, 위와 같이 비교하는데, 현재 수에서 2를 나눈 수의 연산횟수를 비교한다.

3. N이 3으로 나누어 떨어지면서 2로 나누어 떨어지는 경우도 있다. 바로 6의 배수일 경우이다. 이 때는 현재 수에서 2를 나눈 연산횟수, 현재 수에서 3을 나눈 연산횟수중 더 작은 수를 찾아 구한 뒤 1을 더해준다.

4. N이 나누어 떨어지지 않을 경우 현재 수에서 1을 뺀 값의 연산횟수에 1을 더해준다.

따져야하는조건이 완성되었다. 이제 2부터 시작하여 주어진 N까지 반복하며 위 조건대로 수행해주면 DP 배열의 N번 인덱스에 N을 1로 만드는 데 필요한 연산 횟수가 저장될 것이다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463_1로만들기 {

	public static void main(String[] args) throws NumberFormatException, IOException {


		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		// 10 -> 9 -> 3 -> 1 = 3
		// 16 -> 8 -> 4 -> 2 -> 1 = 4 ;
		// dp에 N을 나누는 최솟값을 누적시킨다.
		int[] dp = new int[N+1];
		for(int i=2;i<=N;i++) {
			// N이 3으로 나누어 떨어질 때
			if(i%3 == 0) {
				dp[i] = Math.min(dp[i-1], dp[i/3])+1;
			}
			// N이 2로 나누어 떨어질 때
			if(i%2 == 0) {
				dp[i] = Math.min(dp[i-1], dp[i/2])+1;
			}
			// N이 6의 배수일 때
			if(i%3 == 0 && i%2 == 0) {
				dp[i] = Math.min(dp[i/3], dp[i/2])+1;
			}
			// N이 나누어 떨어지지 않을 때
			if(i%3 != 0 && i%2 != 0 ) {
				dp[i] = dp[i-1] + 1;
			}
		}
//		System.out.println();
		System.out.println(dp[N]);


	}

}