성장 노트

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

• 접근

처음에는 while 반복문 돌리면서 3으로 나누기, 2로 나누기, 1빼기 순으로 각 조건을 확인해서 count를 세는 간단한 문제인줄 알았다.

하지만 두번째 테스트 케이스를 보면 10의 경우 10 -> 9 -> 3 -> 1 순으로 3번 만에 만들 수 있지만 위 방식으로 풀게되면 10 -> 5 -> 4 -> 2 -> 1 (2로 나누기 부터 적용되기 때문에) 4번으로 최소 횟수가 안되는 함정이 있다.

다시 접근해보면 메모이제이션을 이용한 재귀를 떠올려볼 수 있다.

• 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Integer[] arr = new Integer[1000001];
        arr[0] = arr[1] = 0;
        System.out.println(recur(arr, N));
    }

    public static int recur(Integer[] arr, int N) {
        if (arr[N] == null) {
            if (N % 6 == 0) {
                arr[N] = Math.min(recur(arr, N - 1), Math.min(recur(arr, N / 3), recur(arr, N / 2))) + 1;
            } else if (N % 3 == 0) {
                arr[N] = Math.min(recur(arr, N / 3), recur(arr, N - 1)) + 1;
            } else if (N % 2 == 0) {
                arr[N] = Math.min(recur(arr, N / 2), recur(arr, N - 1)) + 1;
            } else {
                arr[N] = recur(arr, N - 1) + 1;
            }
        }
        return arr[N];
    }

}

• 해설

6으로 나눠떨어지는 경우 3가지 연산 방법 중 최소값을 찾아가야한다.

3으로 나눠떨어지는 경우는 2로 나눌수 없으니 2 나누기를 제외한 2가지 연산 방법 중 최소값을 재귀호출!

2으로 나눠떨어지는 경우도 3으로 나누는 것과 마찬가지!

이외에 나눠떨어지지 않으면 1을 빼는 연산 방법을 마지막으로 재귀호출한다.

• 다른 풀이

재귀 함수 매개변수를 통해 count 값을 넘겨주면서 진행하는 방법이 있다.

• 회고

메모이제이션까지 방법을 생각해냈지만 구현까지 성공하지 못했다.

계속 문제를 풀면서 구현 능력을 키우면 쉽게 구현할 수 있을 것 같다.

시간 복잡도 O(N)...?

공간 복잡도 O(N)

바텀 - 업 방법으로도 구현해보자

• 참고

https://st-lab.tistory.com/133