133. 1463(1로 만들기)

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int[1000001];

		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;

		for (int i = 4; 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]);
	}
}

문제요약

조건 1: 3으로 나눠지면 3으로 나눈다

조건 2: 2로 나눠지면 2로 나눈다

조건 3: 1을 뺀다.

세가지 조건을 가장 적게 사용해서 1로 만들어라.

설명

먼저 3까지는 기본값으로 초기화 해준다.

 

입력값이 6인 경우까지 설명 하겠다.

1. 4인경우

1)  1을 뺏을 경우 -> 4 - 1 = 3 

3을 1로 만드는 최소값은 1이다. 

따라서 1(1을 빼는 조건 사용) +  1(3을 1로 만드는 최소값) = 2

 

2)  4를 2로 나눈 경우 -> 4 / 2 = 2 

2를 1로 만드는 최소값은 1이다

따라서 1(2로 나누는 조건 사용) + 1(2를 1로 만드는 최소값) = 2

 

최소값 : 2

2. 5인경우

1)  1을 뺏을 경우 -> 5 - 1 = 4

4를 1로 만드는 값은 2이다.

따라서 1(1을 빼는 조건 사용) +  2(4를 1로 만드는 최소값) = 3

 

최소값 : 3

3. 6인경우

1)  1을 뺏을 경우 -> 6 - 1 = 5

5를 최소로 만드는 최소값은 3이다.

따라서 1(1을 빼는 조건 사용) +  3(5를 1로 만드는 최소값) = 4

 

2)  6을 3으로 나눈 경우 -> 6 / 3 = 2

2를 1로 만드는 최소값은 1이다.

따라서 1(3으로 나누는 조건 사용) + 1(2를 1로 만드는 최소값) = 2

 

3) 6을 2로 나눈 경우 -> 6 / 2 = 3

3을 1로 만드는 최소값은 1이다.

따라서 1(2로 나누는 조건 사용) + 1(3을 1로 만드는 최소값) = 2 

 

최소값 : 2

 

---

			dp[i] = dp[i - 1] + 1;

전 조건에 최소값 + 1 하면 현재 index i의 1을 뺏을 경우 최소로 1로 만드는 경우이다.

 

			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3] +1);
			}

1을 뺏을 경우 1로 만드는 최소값과  3으로 나눴을 때 해당 인덱스의 1로 만드는 최소값 + 1 중 더 작은 값을 저장한다.

 

			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2] +1);
			}

2로 나누어 떨어질 경우이다.

만약 3으로도 나누어 떨어지면, 위에서 조건3과 조건2중 dp[i] 최소값을 저장했다.

따라서 여기서는 조건3과 조건2중 dp[i] 최소값과 2로 나눈 해당 인덱스의 1로 만드는 최소값 + 1 중 더 작은 값을 저장한다.