[BOJ] 1463: 1로 만들기 - DP (JAVA)

1463번: 1로 만들기

 

1463: 1로 만들기를 DP를 사용해서 다시 풀어봤다.

 

풀이

 

재귀함수는 Top-down 방식이고, DP는 Bottom-Up 방식이다.

점화식(작은 문제를 해결해서 큰 문제를 해결하는 방법)을 활용한 다이나믹 프로그래밍 방식이다.

이 방식은 부분 규칙을 활용해서 전체 문제를 푸는 방식인데, DP로 문제를 풀려면 DP인지 아닌지 확인하는 것이 중요하다고 한다.

 

1을 만들어야하니까, 0에서 부터 확인을 한다면,

dp[1] = 0;
1은 0이다. 왜냐면 2로 나눠지지도 않고, 3으로 나눠지지도 않기 때문.
그리고 마지막 1이 되면 끝나기 때문에 0.

 

그럼 이 다음 어떻게 해야할까? 

2가 1이 되려면 2가지 방법이 있다.

1) 2로 나누기.

2) 1을 빼기.

이를 식으로 만들면

dp[2] = dp[1] + 1;
//1

dp[2] = dp[2/2] + 1;
//1

 

그럼 3이 1이 되려면 어떻게 해야할까?

1) 3으로 나누기.

2) 1을 빼고 2로 나누기.

3) 1을 3번 빼기.

dp[3] = dp[3/3] + 1;
// 1

dp[3] = dp[2] + 1;
//2

dp[3] = dp[1] + 1 + 1;
//2

 

그럼 이럴 경우 우리는 연산을 사용하는 최소 횟수를 출력해줘야 하기 때문에, 

Math.min을 사용해줘야 한다.

매 분기마다 3으로 나눠지거나 1을 빼야하고, 2로 나눠지거나 1을 빼야하기 때문에

1을 뺐을 때의 횟수와 숫자로 나눌때의 횟수를 비교해 더 작은 값을 저장해줘야한다.

 

package 백준renew;

import java.io.*;

public class 실버3_1463_1로만들기_2 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		int dp[] = new int[N+1];
		
		dp[1] = 0;
		for(int i=2; i<=N; i++) {
			dp[i] = dp[i-1] + 1;
			if(i%2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2]+1);
			}
			if(i%3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3]+1);
			}
		}
		
		sb.append(dp[N]);
		bw.write(sb.toString());
		bw.close();
	}
}