백준 - 1463(1로 만들기) - DP - Java

1. 문제

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

2. 풀이

N에서 차례대로 내려가서 생각해볼려 했지만, Math.min이 잘 먹히지 않았다.

따라서 2부터 위에서부터 올라가면서 생각하는 것이 편하다. 즉
i에서 곱해서 올라가지 말고, 나눴을때 밑에서 끄집어서 올라와서 dp를 해주는 것이다. 작은 문제에서 큰 문제를 가는 것을 잊지 말지

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);
}

3. 전체 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		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]);

	}

}