[백준 1463번 / Java] 1로 만들기

 

이 문제는 각 숫자마다 최소 연산의 횟수가 정해지기 때문에 각 숫자에 대한 연산 횟수를 기억해두고 사용하는 것이 효율적이다.

내가 헷갈렸던 부분은 연산의 순서였다. 간단히 생각하기에.. 큰수를 나눠보고 안 되면 2로 해보고 그 다음에 1을 빼면 되겠지.. 근데 아닐 수도 있긴 한데.. 하면서 처음 생각으로 알고리즘을 짰다. 결과는 땡,,

확실하지 않은 내용은 다시 한번 확인하기@@.. 각 경우의 최소값을 찾아서 더하는 방식으로 해결했다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] memo = new int[N + 3];
        memo[0] = 0;
        memo[1] = 0;
        memo[2] = 1;
        memo[3] = 1;
        if (N > 3) {
            for (int i = 4; i <= N; i++) {
                solution(memo, i);
            }
        }
        System.out.println(memo[N]);

    }

    private static void solution(int[] memo, int n) {
        int min = 1000000;
        if (n % 3 == 0) {
            int tmp = n / 3;
            if(memo[tmp] < min) {
                min = memo[tmp];
            }
        }
        if (n % 2 == 0) {
            int tmp = n / 2;
            if(memo[tmp] < min) {
                min = memo[tmp];
            }
        }
        int tmp = n - 1;
        if(memo[tmp] < min) {
            min = memo[tmp];
        }
        memo[n] = min + 1;
    }
}