[C++] 백준 1463번 문제풀이

이 문제를 보면서 생각했던 점은 

2,3 이 나오므로 6의 배수를 고려하여 풀고 

입력 받은 수를 나눠가면서 풀자 였다.

그러나 문제를 풀다보니 입력 받은 수를 나눠서 풀기엔 순서를 고려하기 어려웠다

예시에 나온것 처럼

10 -> 9 -> 3-> 1

10 -> 5 -> 4-> 2->1

위와 같이 10에서 바로 2로 나누는것이 아닌 1을 빼고 3으로 나누는것이 연산 수가 적게 나오고

16 -> 8 -> 4 -> 2 -> 1

16 ->15 ->5 -> 4 -> 2 -> 1

위와 같이 16에서 1을 빼고 나누는것이 아닌 바로 2로 나눠서 푸는것이 연산 수가 적게 나왔다.

나눠서 풀기엔 적합하지 않은 문제였다.

그래서 연산을 하면서 풀기로 하였는데

여기서 DP (동적 프로그래밍)을 사용하여서 풀어야 한다는것을 알게 되었다.

DP를 말만 들어봤지 어떤것인지를 자세히 알게 되었는데

이미 알고 있던 피보나치를 예제로 들면서 설명한것을 보게 되었고 어떤것인지 이해하게 되었다.

DP는 하나의 문제를 한 번만 풀도록 해야하는 알고리즘이다.

여기서 연산이 곱하기 3 또는 곱하기 2 또는 더하기 1이였는데

N이 되기 위해 최소로 필요한 연산자 호출을 구하는 문제인데

결국 N이 되기위해 필요한 연산자 호출은 min 연산을 통해 구할 수 있었다.

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1000001];
int main() {
	int N;
	cin >> N;
	for (int i = 2; i <=N; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)dp[i] = min(dp[i], dp[i / 2] + 1);// i/2 에서 곱하기 2 하게되면 i 
		if (i % 3 == 0)dp[i] = min(dp[i], dp[i / 3] + 1);// i/3 에서 곱하기 3 하게되면 i
       	//6을 생각하지 않아도 되는 이유는 i/3 할때 else if 를 쓰지 않았기 때문이다.
	}
	cout << dp[N];
}		

DP를 알고 쓰는것이 처음이기에 익숙하지 않지만 익숙해지도록 문제를 많이 풀어야겠다.