백준 - 1463번 - 1로 만들기

1463번

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

public class Main {

	static Integer[] dp;

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

	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		dp = new Integer[N+1];
		dp[0] = dp[1] = 0;

		System.out.print(recur(N));

	}
}

초기에 N을 어떻게 1로 만들지 반복문과 조건문을 생각해서 풀려고 했다. 무조건 3으로 나눠지게 로직을 짜려 했는데 체점할때 1초만에 틀렸다고 나왔다...

풀이 방법

1. DP문제라는 것을 인지

   • 작은단위 문제들로 큰단위 문제를 해결할 수 있다.
   • 작은단위와 큰단위 문제들이 반복적으로 나타난다.
     • 이 경우에 시간복잡도를 줄이기 위해 배열에 단위문제들을 저장해서 필요할때 꺼내쓰는 개념
     • 피보나치수열 참고
       

2. 점화식과 배열에 메모라이징하기

   • dp문제를 인지해도 점화식을 찾을 수 없다면 문제해결이 힘들다. 그래서 많은 dp문제를 풀면 느낌을 찾는게 도움이 될 듯 하다.
   • 수도 없이 반복이 되는 피보나치 수열 모양에서 한번 해결한 케이스를 배열에 저장해 다시 계산하지 않고 필요할때 배열에서 꺼내쓴다.

     배열에 저장하고 꺼내쓰는 것이 시간복잡도를 어마어마하게 줄여준다.