[BOJ 1463] 1로 만들기 JAVA

---

문제풀이

예제를 보면 10 입력 시 3을 출력해야된다.

최소 연산 횟수이기 때문에 10 -> 9 -> 3 -> 1 의 과정을 거치기 때문이다.

쉬운문제인 줄 알고 조건식만 냅다 써버리면 10 -> 5 -> 4 -> 2 -> 1 과정이 된다.

1. N+1만큼의 DP 메모리 생성

DP{ 0 0 0 0 0 0 0 0 0 0 0 }

D[i]는 1를 만들 수 있는 가장 작은 경우의 수로 생각하면 된다.

2. 배열 앞에서부터 숫자 1를 만들 수 있는 경우의 수를 생각한다.

예를 들어 2를 1로 만들 수 있는 경우의 수는 한가지밖에 없다.
그럼 DP{ 0 0 1 0 0 0 0 0 0 0 0 } 로 변하겠지?

이번엔 3으로 생각해보자. 3이 1이 될 수 있는 경우의 수는 두가지가 있다.
3 -> 2 -> 1일 경우 D[2]+1=2가 된다.
3 -> 1일 경우 D[1]]+1=1이 된다.

더 적은 횟수로 생각해야하므로 DP{ 0 0 1 1 0 0 0 0 0 0 0 } 로 변하게 된다.

마지막으로 4의 경우도 생각해보면 마찬가지로 두가지의 경우의 수가 있다.
4->3->2->1의 경우 D[3]+1 = 2 이 된다.
4-> 2-> 1의 경우 D[2]+1 = 2가된다.
DP{ 0 0 1 1 2 0 0 0 0 0 0 }

여기선 경우의 수가 같은 2이지만 어쨋든 공통로직을 생각할 수 있게된다.

i를 3이나 2로 나눌 수 있는 경우엔 D[i/2]+1 혹은 D[1/3]+1 을 하면 된다.
3이나 2로 나눠떨어지지 않는 경우엔 D[i-1]+1을 하면 된다.

코드

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

		Dp[0] = 0; Dp[1] = 0;

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

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

---

DP적 사고 너무 어렵다 😭 나조차도 완벽하게 이해하지 못하니 설명이 개똥같네