[백준]1463 - 1로 만들기 문제 풀이(Java,자바)

1463번: 1로 만들기

 

들어가며

보자마자 이게 뭔가 싶은 문제였다.

범상치 않은 시간 제한이랑 정답 비율..

그래서 브루트 포스로 푸는 것이 아니라고 직감했고 바로 DP가 생각이 났다.

최근에 풀었던 설탕배달 문제가 생각이 나서 그 때 풀었던 방식을 접목했다.

 

풀이법

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int[] dp = new int[n + 1];

        dp[1] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        System.out.println(dp[n]);
    }

 

Memoization 기법을 이용한 Bottom Up 방식을 사용한다.

쉽게 말해 배열을 만들어 이전 상태들을 저장해두고 처음부터 하나하나씩 계산해 최종 결과물을 얻는 과정을 거친다.

 

이 dp 배열에서 인덱스는 숫자 n을 의미하며, n일 때 가장 최소의 연산 횟수를 가지고 있다고 생각한다.

그러면 어느 숫자 n이 있으면 그 숫자는 3개의 이전 상태에서 비롯된다.

+1 하기 전 상태, *2 하기 전 상태, *3 하기 전 상태

이 3가지 상태에서 중에서 최소값을 찾은 뒤 거기서 1만 더해주면 n일 때, 최소 연산 횟수가 되는 것이다.

 

다만, 여기서 변수로 2와 3의 공배수인 6이 있기 때문에 %2, %3을 두 번 처리함으로써 /2, /3 상태와의 비교를 유도한다.

 

최종적으로는 dp[n] 을 표시하면 답이 나온다.

 

추가로, dp[1] = 0을 초기화 한다. 문제에선 1보다 큰 경우만 보고 있기 때문에, 반복문에서 등장하는 dp[1]를 처리해줘야 한다.