백준 1463 c++ "1로 만들기" -PlusUltraCode-

https://www.acmicpc.net/problem/1463

 

 

[필자 사고]

이 문제는 최대 N값이 크지 않아 DFS를 이용해도 되고 BFS 탐색을 이용해도 된다.

필자는 동적프로그래밍을 이용하여 이 문제를 해결 했따.

 

필자는 DP설계 방식을 bottom-up 방식으로 설계했다.

일단 dp[i] = dp[i-1]+1로 << 1을뺀다라는 조건이 있으므로 강제로 1증가

그다음 if(i%3==0) , if(i%2==0) 두개의 식을 이용하여 

더 작은 값을 dp[i] 로 갱신하는 형태로 코드를 완성했다.

 

ex) dp[i] = min(dp[i], dp[i/3]+1);

 

[코드 해설]

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int N;
vector<int> dp;

void Game_Start() {
	cin >> N;
	dp.resize(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] = min(dp[i ], dp[i / 3]+1);
		}
		if (i % 2 == 0) {
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
	}

	cout << dp[N];

}

int main(void) {
	Game_Start();
}