[백준 1463] 1로 만들기

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

 

DP문제입니다.

연산을 수행하는 경우가 3가지가 있죠

1.  X%3 == 0

2.  X%2 == 0

3.  X-=1

배열을 사용해 X까지의 최소 연산 횟수를 구할겁니다.

만약 X가

1일 경우 연산 횟수 -> 0   arr[1] = 0;

2일 경우 ->  2가지 경우가 가능하죠. 나누든지 빼든지. 

                 나눌경우 다음값을 1이 되면서 arr[2] = arr[1] + 1,  결과 : 1

                 1을 뺄경우 다음값이 1이 되면서 arr[2] = arr[1] + 1,  결과 : 1

                 동일하네요 

3일경우 -> 역시 2가지 경우.

               나눌경우 다음값을 1이 되면서 arr[3] = arr[1] + 1,  결과 : 1

               1을 뺄경우 다음값이 2가 되면서 arr[3] = arr[2] + 1,  결과 : 2

               두가지의 결과값이 다릅니다.

4일경우 -> 2가지

               나눌경우 다음값이 2가 되면서 arr[4] = arr[2] + 1, 결과 : 2

               1을 뺄경우 다음값이 3이 되면서 arr[4] = arr[3] + 1, 결과 : arr[3]의 두가지 경우 중 최소값 + 1

 

이런 방법으로 X까지.

결과적으로 어느 수 X의 최소 1을 만들기위한 연산 횟수는

세가지 연산이 모두 가능하다고 쳤을경우

X/2 까지의 최소 연산횟수

X/3 까지의 최소 연산횟수

X-1 까지의 최소 연산횟수

세가지중 제일 작은 값에 현재 행동값 1을 더하면 됩니다.

 

public class Q1463 {
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		/*
		 * X가 2로 나누어 떨어지면 2으로 나눔
		 * X가 3로 나누어 떨어지면 3로 나눔
		 * 1을 뺌
		 */
		arr = new int[num+1];
		
		arr[1] = 0;
		for(int i=2; i<=num; i++) {
			int c1 = 1000001;
			int c2 = 1000001;
			int c3 = 1000001;
			
			if(i%2==0) {
				c1 = arr[i/2];
			}
			if(i%3==0) {
				c2 = arr[i/3];
			}
			c3 = arr[i-1];
			arr[i] = Math.min(Math.min(c1, c2), c3)+1;
		}
		System.out.println(arr[num]);
		}
}