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

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

1463번: 1로 만들기

1. 문제

 

 

2. 풀이

숫자n을 입력받고 1부터 n까지의 최소연산횟수를 저장하는 배열을 만든다. 배열의 디폴트 값은 다음과 같다.

cnt[1]=1 

cnt[2]=1

cnt[3]=1 

---

그 다음으로 n=4 즉, 정수 4가 입력되었을때의 연산을 사용하는 횟수는

1) 4를 2로 나누는 경우 2) 4에서 -1을 빼는 경우

이 두가지로 나눌수가 있다.

1) 4→2→1 밑줄친 부분은 cnt[2]와 같다.

2) 4→3→1 밑줄친 부분은 cnt[3]와 같다.

즉, cnt[2]와 cnt[3]은 앞에서 이미 계산되었으므로 이 중  더 작은 값이 나오는 경우를 따져서 cnt[n]을 구하면 된다.

여기서는 cnt[2]=cnt[3]=1으로 같기 때문에 cnt[4]=1(2로 나누거나 -1로 빼는경우 연산1회)+1=2가 된다.

이와 같이 앞에서 이미 계산된 Subproblem으로 원래 문제를 해결하므로 dp방식으로 문제에 접근할 수 있다.

n이 2의 배수, 3의 배수, 2와 3의 공배수, 2와 3의 공배수가 아닌 경우 총 4가지의의 경우에 대한 점화식은 다음과 같다.

 

i) n이 2의 배수인 경우

ex) cnt[8]=최소값(2로 나누는 경우, 1을 뺀 경우)+1

 

ii) n이 3의 배수인 경우

ex) cnt[9]=최소값(3으로 나누는 경우, 1을 뺀 경우)+1

 

iii) n이 2,3의 공배수인 경우

ex) cnt[6]=최소값(3으로 나누는 경우, 2로 나누는 경우, 1을 뺀 경우)+1

 

iiii) n이 2,3의 공배수가 아닌 경우

ex) cnt[7]=(1을 뺀 경우)+1

 

 

3. 소스코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] cnt = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			if (i == 1) {
				cnt[i] = 0;
			} else if (i == 2 || i == 3) {
				cnt[i] = 1;
			} else {
				if (i % 2 == 0 && i % 3 != 0) { // 2의 배수만
					cnt[i] = Math.min(cnt[i - 1], cnt[i / 2]) + 1;
				} else if (i % 3 == 0 && i % 2 != 0) {// 3의 배수만
					cnt[i] = Math.min(cnt[i - 1], cnt[i / 3]) + 1;
				} else if (i % 2 == 0 && i % 3 == 0) {// 2,3 공배수
					int small = cnt[i - 1];
					if (cnt[i / 2] < small) {
						small = cnt[i / 2];
					}
					if (cnt[i / 3] < small) {
						small = cnt[i / 3];
					}
					cnt[i] = small + 1;
				} else {// 2,3배수 아님
					cnt[i] = cnt[i - 1] + 1;
				}
			}
		}

		System.out.println(cnt[n]);

	}

}