[Baekjoon]1436번 1로 만들기

1. 문제

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

2. Source

https://github.com/lalwr/algorithm/blob/master/src/Baekjoon/algorihtm_1436.java

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

public class Algorigtm_make1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        dp[1] = 0;

        for(int i=2;i<=N;i++) {
            dp[i] = dp[i-1]+1;
            if(i%2==0) dp[i] = dp[i/2]+1 > dp[i] ? dp[i] : dp[i/2]+1;
            if(i%3==0) dp[i] = dp[i/3]+1 > dp[i] ? dp[i] : dp[i/3]+1;
        }
        System.out.println(dp[N]);

    }
}

3. 풀이

dp[i] 의 최소 횟수는 dp[i-1] + 1 , dp[i/2] + 1 , dp[i/3] + 1 값을 비교해서 최소 값을 저장하면 된다.