1463 1로 만들기 JAVA

 

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

 

우선 DP는 큰 문제를 작은 문제로 나누고, 그 작은 문제들의 값으로 큰 문제를 구하는 것이다.

Dinamic Programin이라고도 하며, 동적계획법이라고도 한다.

 

DP를 풀 때 Bottom Up과 Top Down 방식이 있다.

Bottom up은 작은 문제들부터 계산해서 큰 문제를 구하는 것이고, Top Down은 이의 반대이다.

 

이 둘의 차이는 크게 없지만 약간은 다르다.

Top Down 방식은 재귀하면서 스택을 쌓아가기 때문에 StackOverFlow 에러가 뜰 수 있다.

따라서 자바, C언어는 딱히 상관 없지만 파이썬은 Top Down보다 Bottom Up이 더 낫다고 생각한다.

 

나는 자바 언어고, Top Down 방식이 더 마음에 들어서 이 방식으로 공부를 하려고 한다.

 

그럼 문제 풀이를 해보려고 한다.

 

이 문제는 X를 최대한 적은 연산으로 1을 만들어야 하는 것이다.

나와 같이 DP를 처음 접해봤다면 이렇게 생각할 것이다.

 

"3으로 먼저 나누고, 나눌 수 없다면 2로 나누고, 이것도 못나누면 1을 빼면 되지 않나?"

이 방식은 결론부터 말하자면 절대 답을 구할 수 없다. 반례는 문제의 힌트에 적혀있다.

 

그럼 어떻게 풀 수 있을까?

아래 테이블의 좌측에 X를, 우측에 X의 최소 연산 횟수를 정리해보겠다.

 

번	값
1	0
2	1
3	1
4	2
5	3
6	2
7	3

여기엔 한 가지 규칙을 찾아볼 수 있는데, 

 

X가 만약 4인 경우, 내가 할 수 있는 연산은 " / 2" 또는 " - 1"이다. 그렇게 되면 4/2번의 값과 4-1번의 값 중 작은 것으로 연산하면 된다.

4/2 = 1; 4-1 = 1; 이 경우에 동일하므로 어딜 가던 상관 없다.

 

 

X가 6인 경우, 내가 할 수 있는 연산은 모두 가능하다. 따라서 "6 / 3"번, "6 / 2"번, "6 -  1"번중 가장 작은 값을 구해서 그것으로 연산하면 된다. 6/3 = 1; 6/2 = 1; 6-1 = 3; 이 경우에 3으로 나누거나 2로 나눈 경우로 가면 된다.

 

X가 7인 경우엔? 2나 3으로 나눌 수 없으므로 -1을 한 6으로 가야 한다. 그리고 6에서는 아까 위에서 값을 구했으므로 이 값을 사용해서 더해버리면 끝이다.

 

 

이론적으로 풀어 설명해봤는데 이해가 되었으면 좋겠다.

개발자는 말 보다 코드이므로 바로 코드를 보여보겠다.

 

import java.io.*;
public class D1463 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        D = new int[X+1];
        System.out.println(makeOne(X));
    }
    private static int[] D;
    public static int makeOne(int num) {
        if(num < 2) return 0;

        else if(D[num] != 0)
            return D[num];

        D[num] = makeOne(num - 1) + 1;

        if(num %3 == 0) {
            int tmp = makeOne(num / 3) + 1;
            if(D[num] > tmp) D[num] = tmp;
        }

        if(num %2 == 0) {
            int tmp = makeOne(num / 2) + 1;
            if(D[num] > tmp) D[num] = tmp;
        }

        return D[num];

    }
}

이 코드의 로직은 간단하다. 아까 위에 테이블을 정리한 것을 보았듯이 2 미만의 값은 무조건 0이므로 return 0을 해주었다.

 

그리고 이러한 재귀의 성능을 올려주는 else if문이 중요하다고 생각한다.

else if(D[num] != 0)
    return D[num];

이 부분인데, 이미 구한 값이 num으로 넘어오는 경우가 있다. 이해가 안된다면 노트에 그려보면 이해할 수 있을 것이다.

모든 배열의 초기 값은 0인데 배열의 값이 0이 아니라는 것은 값을 전에 이미 구했다는 얘기가 된다.

따라서 값을 구한 경우에 또 구하라고 재귀 시켜버리지 말고, 바로 자신을 호출한 스택으로 값을 돌려준다.

이것을 "memoization"이라고 한다.