1463

 

1로 만들기

 

아래 포스트에 설명이 좋다.

https://jae04099.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1463-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

 

가능한 연산

1, 2로 나눈다

2, 3으로 나눈다

3, 1을 뺀다

 

1을 가장 먼저 빼는 이유?

아래코드의 틀린점이라고 하면..

안해봤지만 dp[i] = dp[i-1] + 1 를

dp[i] = Math.min(dp[i], dp[i-1] + 1)로 고쳐주면 될거 같다.

위에서 2,3으로 최적화된 값 구해 놓고, dp[i-1] + 1로 업데이트하면 이전 계산값을 OverWrite

 

 

//Discussion에서 찾은 코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		for (int i = 2; i < dp.length; i++) {
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1;
			}
			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
			}
			if (i % 3 != 0 && i % 2 != 0) {
				dp[i] = dp[i - 1] + 1;
			}
		}
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println("dp[" + i + "] +  : " + dp[i]);
//		}
		System.out.println(dp[n]);
	}
}

30
[2 1]
[3 1]
[4 2]
[5 3]
[6 2]
[7 3]
[8 3]
[9 2]
[10 3]
[11 4]
[12 3]
[13 4]
[14 4]
[15 4]
[16 4]
[17 5]
[18 3]
[19 4]
[20 4]
[21 4]
[22 5]
[23 6]
[24 4]
[25 5]
[26 5]
[27 3]
[28 4]
[29 5]
DBG1[30 4]
DBG2[30 5]
DBG3[30 5]
[30 5]
5

디버깅 메시지를 넣고 출력을 해보면, 이미 최적값을 구해 놓고, 저장한 값을 참조하지 않고 비교하기 때문에 

잘못된 값이 저장되는 것을 확인할 수 있다. 

고찰 : 최적값을 구해야 하는 경우에는 저장된 값을 비교해야 이런 실수가 없지 않나 싶다.

 

 

//정답
import java.util.Scanner;

class Main {
	static int n;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] dp = new int[n + 1];

		dp[0] = 0;
		dp[1] = 0;
		for (int i = 2; i < dp.length; i++) {
			dp[i] = dp[i - 1] + 1;
			if (i % 3 == 0)
				dp[i] = Math.min(dp[i], dp[i / 3] + 1);
			if (i % 2 == 0)
				dp[i] = Math.min(dp[i], dp[i / 2] + 1);
		}

		System.out.println(dp[n]);
	}

}