<문제> 1로 만들기 (Dynamic Programming)

 

문제 2. 1로 만들기

 

 

 

 

---

 

문제만 봤을 때 그리디를 활용해서 풀려고 했다.

 

 

그런데 그리디로 풀면 안된다. 왜냐하면 예시를 살펴보면 입력이 26일 때

 

 

그리디를 사용하면 우선 순위가 5로 나누기, 3으로 나누기, 2로 나누기, -1 빼기

 

 

순서가 될 것이기 때문에

 

 

26 -> 13 -> 12 -> 4 -> 2 -> 1 순서로 될 것이기 때문에

 

 

최소 연산인 26 -> 25 -> 5 -> 1 이 수행될 수 없다.

 

 

 

 

 

그래서 DP를 활용할 방법을 살펴볼 것이다.

 

 

 

 

함수가 호출되는 과정을 살펴보면 입력으로 6이 들어왔을 때

 

 

-1을 한 값인 f(5), ÷3을 한 값인 f(3), ÷2를 한 값인 f(2) 로 나누어 지며

 

그 밑으로 f(1)이 나올 때까지 뻗어갈 수 있다.

 

 

 

이렇게 작은 문제들을 조합해서 해결될 수 있기 때문에

 

 

DP를 적절히 사용할 수 있다.

 

 

 

 

 

 

-1을 했을 경우와 i를 2,3,5 중에서 나눌 수 있을 경우 그 몫들 중에서 가장 작은 수를 Ai에 넣어주며

 

 

문제인 횟수를 구하기 위해 +1을 해준다.

 

 

 

 

코드

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


public class Make1 { // 1로 만들기 DP
	
	public static int d[] = new int[30001]; // DP 테이블, 연산의 횟수
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int X = Integer.parseInt(br.readLine());
		
		for(int i = 2; i <= X; i++) {
			
			// -1을 하는 경우
			d[i] = d[i - 1] + 1;
			
			// ÷2 하는 경우
			if(i % 2 == 0)
				d[i] = Math.min(d[i], d[i / 2] + 1);
			
			// ÷3 하는 경우
			if(i % 3 == 0)
				d[i] = Math.min(d[i], d[i / 3] + 1);
			
			// ÷5 하는 경우
			if(i % 5 == 0)
				d[i] = Math.min(d[i], d[i / 5] + 1);
		}
		
		System.out.println(d[X]);
	}

}

 

 

 

 

 

 

 

출처 : https://www.youtube.com/watch?v=5Lu34WIx2Us&t=1495s