[백준] 1463번 (1로 만들기)

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

1463번: 1로 만들기

---

1. 아이디어

: 동전바꾸기 문제와 같은 메커니즘. 아래 3가지 경우의 수 중 최솟값 구한 후 +1 한 값을 다음 배열에 저장.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

• 점화식 :
  1. F(n) = F(n-1) + 1
  2. (X%2 == 0 일때) F(n) = Min(F(n), F(n/2) + 1)
  3. (X%3 == 0 일때) F(n) = Min(F(n), F(n/3) + 1)
• 최솟값 알기 위해 Math.min() 메소드 사용
• dp[0] 과 dp[1] 의 값은 0이다.
• N값 구하기 위해, for 문 2 부터 N까지 값 구해서 dp 배열 저장

---

2. 코드

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[n+1];
		dp[0] = 0;
		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);
		}
		System.out.println(dp[n]);
	}
}