1로 만들기

https://www.acmicpc.net/problem/1463
정수 n이 주어질 때 다음 세 연산을 최소로 사용해 1로 만드는 문제이다.

1. x % 3 == 0이면 3으로 나눔
2. x % 2 == 0이면 2로 나눔
3. 1을 뺀다

메모이제이션을 사용해 O(n)에 해결할 수 있다.

import java.io.*;

public class Main
{
    public static int func(int n) 
    {
        int[] dp = new int[n+1]; // 인덱스 1부터 시작
        dp[1] = 0;
        //dp[2] = 1;
        //dp[3] = 1;
        for (int i=2; i<=n; i++)
        {
            // dp[i]를 i-1의 최솟값에 1더한 값으로 우선 설정
            dp[i] = dp[i-1] + 1;
            if (i%3 == 0) // 3으로 나누어 떨어질 때
            { // 미리 설정해둔 dp[i]와(1을 빼는 연산) 3으로 나누는 연산 
            // 비교해서 더 작은 값으로 설정
                dp[i] = Math.min(dp[i/3] + 1, dp[i]);
            }
            if (i%2 == 0) // 3,2둘다 나눠지는 수도 있으니 else if 아닌 if
            {
                dp[i] = Math.min(dp[i/2] + 1, dp[i]);
            }
        }
        
        return dp[n];
    }

	public static void main(String[] args) throws IOException
	{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
		System.out.println(func(n));
	}
}