[백준 1463 / JAVA] 1로 만들기

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

1463번: 1로 만들기

 

DP 문제라 풀이 방식이 매우 많다.

Bottom-Up 방식도 있고 Top-Down 방식도 있다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] a;

    public static void main(String[] args) throws IOException {
        int N;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        a = new int[N + 1];

        for (int i = 2; i <= N; i++) {
            a[i] = a[i - 1] + 1;

            if (i % 3 == 0)
                a[i] = Math.min(a[i], a[i / 3] + 1);

            if (i % 2 == 0)
                a[i] = Math.min(a[i], a[i / 2] + 1);
        }

        System.out.println(a[N]);
    }
}

먼저 1 작은 수에서 1을 더한 횟수를 구하고 만약 2나 3으로 나눠지면 그 경우와 비교해 저 적은 수를 저장한다.

이를 N까지 반복한다.