백준(baekjoon) [JAVA] - 1463번: 1로 만들기

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

1463번: 1로 만들기

---

import java.io.*;

// 1로 만들기
public class _1463 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int x = Integer.parseInt(br.readLine());
        int[] arr = new int[x + 1];

        for (int i = 2; i <= x; i++) {
            arr[i] = arr[i - 1] + 1;
            if (i % 2 == 0) {
                arr[i] = Math.min(arr[i / 2] + 1, arr[i]);
            }
            if (i % 3 == 0) {
                arr[i] = Math.min(arr[i / 3] + 1, arr[i]);
            }
        }
        bw.write(arr[x] + "");

        bw.flush();
        bw.close();
    }
}

---

MEMO

-- 10과 같은 여러 가지의 경우가 생길 때 어떻게 처리해야할지 잘 생각해야함

-- 10은 처음에 2로 나누고 시작하는 방법, 1을 빼고 9의 경우에서 시작하는 방법이 존재

-- 이러한 경우 어떤 방법이 연산을 최소화 할지 알기 힘듬

-- 따라서 Math.min()을 통해서 둘의 방식을 모두 연산 후 작은 값을 고르도록 함

 

!! 동적 프로그래밍 적용이 가능한 문제 특징 잘 파악하기 !!