[DP] 1463번

Bottomup 방식과 Topdown 방식이 있는데 일단 Bottomup 방식으로 풀었다.

n이 주어지면 2부터 n까지 for문이 돌면서 조건에 맞게 주어진 세개의 연산을 풀어낸다.

나누어 떨어지면이므로 if를 통해 검사하고 디폴트로 먼저 i 바로 전에서 구한 dp[i] 값에 +1을 해준다.

(2와 3으로 나누어지지 않아도 이미 연산을 한번 수행한 것이므로)

 

이후 2또는 3으로 나누어지면 그때 i와 i를 2 또는 3으로 나눈 값을 비교하여 작은 값을 dp[i] 에 넣어준다.

 

계속 헷갈렸던 것이 i의 값과 dp배열 각각의 원소의 값인데 

각각의 원소의 값은 연산을 한 횟수이다. 출력되는 부분을 확인하면 쉽게 생각할 수 있음..

 

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		int dp[] = new int[n+1];
		dp[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]);
	}
}