[알고리즘] 백준 1463 자바 JAVA 동적프로그래밍

솔직히 말해서 여태 풀었던 문제들은 점화식을 이용해서 이전 계산 값을 가지고 푸는 문제였는데, 이번 문제는 조금 달랐다. (물론 생각의 전환 차이였고 같은 유형임) 이 문제는 메모이제이션이라고 해서 값을 적어둔다 이런 느낌의 문제다.

 

이게 사람 사고가 문제가 뭐냐면 중고등학교때 학교 학원에서 익힌 기출(?)에 의한.. 주입식.. 크흠 아무튼 사고 자체를 확장하지 않으면 아닌걸 알면서도 if문 써서 풀어보다가 결국 빠꾸치는 문제가 된다.

 

이 문제를 사고하는 방식은 지름길을 뒤늦게 찾는(?) 문제라고 보여졌다. 0과 1일때는 어차피 계산할게 없으니 0을 넣어주고 2부터 진행하는데 이전의 연산 횟수를 계속 업데이트 하되, 1번씩 연산했다고 가정하고 진행하는 것이다. 여기서 1번씩 연산했다고 가정하는 방식은 +1을 추가해줘서 진행을 한다. dp[i] = dp[i - 1] + 1; 이걸 먼저한 이유는 i가 2나 3으로 나누어 떨어지지 않을수도 있기 때문에 먼저 1을 추가한 뒤에 뒤의 if문에 따라서 참의 경우에 i를 나눈 값의 인덱스에 위치한 값을 가져오고 연산을 1 추가하는 방식을 이용한 것이다. 만약 2나 3으로 나누어지지 않으면 우리가 할 수 있는 것은 오직 1을 뺀다라는 3번째 조건밖에 존재하지 않는다. 그 작업을 해주는 것이 dp[i] = dp[i - 1] + 1; 이 줄이다. 2로 3으로 나누어질지는 그 다음 문제이다.

 

2와 3으로 나누어지면 i/2 i/3과 비교해서 더 연산 횟수가 작은 놈이 누구인지 구해내면 된다.

 

Top-Down, Bottom-Up 방식 모두 구현한 코드

public class BaekJoon_16_1463 {

	private static BufferedWriter writer;
	private static int[] dp;

	private static int recur(int n) {
		if (n == 1)
			return 0;
		if (dp[n] > 0)
			return dp[n];
		dp[n] = recur(n - 1) + 1;
		if (n % 2 == 0)
			dp[n] = Math.min(dp[n], recur(n / 2) + 1);
		if (n % 3 == 0)
			dp[n] = Math.min(dp[n], recur(n / 3) + 1);
		return dp[n];
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new BufferedWriter(new OutputStreamWriter(System.out));
		dp = new int[1000001];

		int n = Integer.parseInt(reader.readLine());

		dp[0] = 0;
		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);
		}

		writer.write(dp[n] + "\n");
		writer.write(recur(n) + "\n");

		writer.flush();
		reader.close();
		writer.close();
	}
}