[백준 / 실버3] 1463 1로 만들기 (Java)

문제 보기

사용한 것

• 1을 가장 적은 연산 횟수로 만드는 것을 계산하기 위한 bottom-up

풀이 방법

• d의 1 번째 인덱스에 0을 넣고, i = 2 부터 num까지 1을 빼서 구한 것, 2로 나눠서 구한 것, 3으로 나눠서 구한 것 중 가장 적은 횟수를 d의 i 번째 인덱스에 저장한다.
• d의 num 번째 인덱스의 값을 출력한다.

코드

public class Main {

    public static int[] d;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        d = new int[num + 1];
        d[1] = 0;
        for (int i = 2; i <= num; i++) {
            d[i] = d[i - 1] + 1;
            if (i % 2 == 0) {
                d[i] = Math.min(d[i / 2] + 1, d[i]);
            }
            if (i % 3 == 0) {
                d[i] = Math.min(d[i / 3] + 1, d[i]);
            }
        }

        System.out.println(d[num]);
    }
}