문제

DP를 제대로 이해하지 못해서 엄청 헤매서 정리를 해보려고 한다.

DP

Dynamic Programming으로 큰 문제를 해결하기 위해서 작은 문제부터 차례로 해결해나가서 그것들로 큰 문제를 해결하는 방법이다. 피보나치 수열 (f(N) = f(N-1)+f(N-2);)이 DP문제의 대표적인 예시이다.

DP 문제 해결 방법

1. 어떤 것이 재사용되는 값인지 파악하고 이를 변수로 지정한다.
2. 그 변수들로 점화식을 만든다.
3. 변수의 값들을 모두 저장해둔다.
4. 기저조건 파악한다.

Bottom-Up 방식

반복문 사용
dp[0]부터 계산해서 dp[N]을 구하는 방법

Top-Down방식

재귀 사용
dp[N]을 구하기 위해서 dp[0]까지 내려간 다음에 해당 값을 재귀로 전달시켜서 재사용하는 방식

1463번 _ 1로 만들기

맨 처음에는 Top-Down방식으로 풀었는데, 시간초과가 나서 Bottom-Up방식으로 다시 풀었다.
여러 블로그를 참고해도 이해가 잘 안가서 직접 손으로 그려보니까 이해가 잘 되었다!
minCnt[] = min(minCnt[i-1]+1,minCnt[i/2]+1,minCnt[i/3]+1)을 구하면 되는데, 여기서 각 방법에 1을 더해주는 이유는 밑의 그림 중 N=4일때를 참고하면,
4 -> 3 -> 1 일 때
4 -> 3으로 가는 방법 1번
3 -> 1로 가는 방법 1번으로 이뤄지는데,
4 -> 3 번에서 생기는 1번을 더해주는 것이다.

그래서 짠 코드는 다음과 같다.

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

public class Boj1463 {
	public static int min = Integer.MAX_VALUE;
	public static int cnt =0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		//최소 연산 값 저장
		int minCnt[] = new int[N+1];
		for(int i=2;i<=N;i++) {
        	//-1연산은 무조건 수행
			minCnt[i]=minCnt[i-1]+1;
            //-1연산이랑 2로나누는 연산 중 최소로 연산 수행하는 값
			if(i%2==0) minCnt[i]=Math.min(minCnt[i],minCnt[i/2]+1);
            //6으로 나눠지는 값이라면 2로 나눌 때의 최소연산값과 3으로 나눈 연산 비교
            //아니면, -1연산이랑 3으로 나누는 연산 중 최소로 연산 수행하는 값
			if(i%3==0) minCnt[i]=Math.min(minCnt[i],minCnt[i/3]+1);
		}
		System.out.println(minCnt[N]);
	}
}

참고로, 6으로 나눠지는 값이여도(2,3둘 다 나눠지는 값) 2로 나눌 때 최소값을 minCnt[i]에 저장해두기 때문에 잘 동작한다.