백준 - 1로 만들기

문제 출처: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

필자는 Dynamic Programming 즉, 동적 프로그래밍에 대한 유형에 약하다고 생각이 들어서 문제풀이를 해보았다. 해당 문제와 비슷한 유형을 여러 코테에서 확인할 수 있었고, 입력의 범위 때문에 거의 무조건 DP를 사용하지 않으면 테케를 통과하기 힘들다는 것을 알기 때문에 DP유형 학습을 위해 문제풀이를 해보았다.

 

우선 이문제는 Bottom-Up방식으로 접근했다. 배열의 인덱스가 1,2,3에 각각 0,1,1(걸리는 연산 횟수)이란 값을 넣어주었다. 이 값들의 의미는, 입력으로 1,2,3 이 들어오면 따로 연산이 필요하지 않고 바로 해당 인덱스의 값을 출력해주면 된다는 뜻이다.(1이 입력이면서 동시에 정답이므로 0, 2는 /2를 통해 1번의 연산으로 정답 도출 가능, 3도 2와 같은 방식)

 

4부터는 N까지 진행하면서 /3,/2,-1의 인덱스를 갖는 값들중 최소에서 +1을 해주면 된다. 아래 표로 자세히 설명하겠다.

 

0	1	2	3	4	5	6	7	8	9
-	0	1	1	2

 

1행은 배열의 인덱스, 2행은 해당 인덱스까지의 최소 거리를 나타낸다. 4번 인덱스는 각각 /3, /2, -1번의 인덱스 중에서 최솟값을 구해야 하는데 물론 나누어 떨어지는 인덱스 중에서 찾아야 한다.(그래야 연산 가능한 경로니깐!)

 

-1 인덱스인 3번 인덱스(arr[3])의 1

/2 인덱스인 2번 인덱스(arr[2])의 1

이 둘중에서 최솟값에서 +1만큼 해주면 4번까지의 최소 연산 횟수가 되는 것이다.

이런 방식으로 입력 값까지 진행하면 해당 값까지의 최소 연산 횟수 도출이 가능하다.

 

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int arr[] = new int[1000001];
        arr[1] = 0;
        arr[2] = 1;
        arr[3] = 1;
        int N = Integer.parseInt(br.readLine());
        if (N <= 3) {
            System.out.println(arr[N]);
        } else {
            for (int i = 4; i <= N; i++) {
                int divideByThree = Integer.MAX_VALUE;
                int divideByTwo = Integer.MAX_VALUE;
                int minusOne = Integer.MAX_VALUE;
                if (i % 3 == 0)
                    divideByThree = arr[i / 3] + 1;
                if (i % 2 == 0)
                    divideByTwo = arr[i / 2] + 1;
                minusOne = arr[i - 1] + 1;

                arr[i] = Math.min(divideByThree, Math.min(divideByTwo, minusOne));
            }
            System.out.println(arr[N]);
        }
    }