(Java) 백준 1463 - 1로 만들기

지금까지는 대부분의 코딩 테스트 연습을 프로그래머스에서 했다.
이제 유형별로 다양한 문제를 접해보고 싶어 백준도 틈틈이 풀어보려고 한다.

문제를 처음 읽고 DP가 바로 떠오르지 않았다.
예전에 피보나치 문제를 풀면서 DP를 처음 접했던 기억이 있는데
잘 이해하지 못하고 겨우 풀었던것 같다.
이번에는 DP 문제인걸 알고서도 연습이 안되어 있어 한참을 고생했다.
DP, DFS/ BFS, 최단거리, 그리디를 집중적으로 연습해볼 생각이다.

N에서 1로 만드는 연산의 최솟값을 구하라고 하니 자연스럽게
Top-Down 방식이 먼저 떠올랐다.
재귀를 이용해야 하는데 아직 재귀가 익숙하지 않아 조금 버벅거렸다.
IDE에서는 정답이 나오는데 백준에서는 계속 시간 초과에 걸려서 검색해본 결과
제한 시간내에 통과하기 위해서는 이 조건을 꼭 써야 했다.

// 최솟값보다 카운팅이 많아지면 리턴
if(cnt > answer) return;

Top-Down 방식으로는 메모이제이션을 사용하지 않으니 재귀 호출이 너무 많아져서 그런 것 같다.

Top-Down 방식 코드

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

public class Main {
    // 첫번째 순회에서 int의 최댓값과 answer 비교를 위해 전역 변수 선언
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
    	// Scanner 대신 BufferedReader를 사용해 속도 향상
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader는 String 형식으로만 반환 (Int 형변환)
        int n = Integer.parseInt(br.readLine());
        //topDown 방식
        topDown(n, 0);
        System.out.println(answer);
    }

    static void topDown(int num, int cnt) {
        // 재귀 탈출문
        if(num == 1) {
            answer = Math.min(cnt, answer);
            return;
        }

        // 최솟값보다 카운팅이 많아지면 리턴
        if(cnt > answer) return;

        // 2로 나누어 떨어지면
        if(num % 2 == 0) {
            topDown(num / 2, cnt+1);
        }
        // 3으로 나누어 떨어지면
        if(num % 3 == 0) {
            topDown(num / 3, cnt+1);
        }
        // 그게 아니면
        topDown(num - 1, cnt+1);
    }
}

Bottom-up 방식으로는 도저히 풀이가 떠오르지 않아 검색하여 다른 분들의 풀이를 참고했다.
코드를 보고서도 한참이 걸려 이해했고 아직도 익숙하지가 않다.

Bottom-Up 방식 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Scanner 대신 BufferedReader를 사용해 속도 향상
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader는 String 형식으로만 반환 (Int 형변환)
        int n = Integer.parseInt(br.readLine());
        // bottom-up 방식
        System.out.println(bottomUp(n));
    }

    static int bottomUp(int num) {
        // 1부터 num까지의 배열 선언
        int[] dp = new int[num + 1];
        // num까지 실행해야 함으로 i <= num 까지 or i < num+1 까지
        for (int i = 2; i <= num ; i++) {
            // 1을 빼줬을때 횟수 저장
            dp[i] = dp[i-1] + 1;
            // 2로 나누어 떨어진다면
            if(i % 2 == 0) {
                // 1을 뺴줬을때 횟수와 2로 나눈수의 횟수에 1을 더한 값 비교
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            // 3으로 나누어 떨어진다면
            if(i % 3 == 0) {
                // 1을 뺴줬을때 횟수와 3으로 나눈수의 횟수에 1을 더한 값 비교
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        return dp[num];
    }
}