백준 1463번 : 1로 만들기

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        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]);
    }

    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

dp에 연산에 필요한 횟수를 저장한다. for문으로 bottom-up 방식을 사용한다.

1을 연산하는데 필요한 횟수는 0이다. dp[1]에는 0을 저장한다.

2를 연산하는데 필요한 횟수는 1이며. dp[2]에는 1을 저장한다.

3를 연산하는데 필요한 횟수는 1이며, dp[3]에는 1을 저장한다.

 

만약 4를 연산하는 경우에 필요한 횟수를 구하는 방법은 

4를 -1 했을 경우 / dp[4] = dp[4-1] +1

4를 2로 나누었을 경우 / dp[2] (2를 구하는 연산횟수) + 1 (현재 행하는 연산횟수 1 추가)

중에 작은 횟수를 저장 하는 방식으로

정수 n까지 bottom-up해서 dp에 저장해나간후 원하는 정수 n의 연산 횟수를 출력하면 된다.