[백준] 1463번 1로 만들기 - C++ (dp-동적계획법, bottom-up 반복문)

발상

우선 dp 사용 시 고려해야 할 점 - 부분해가 최적해의 일부분인가? 와 점화식이 존재하는가? 를 고려했을 때, dp[i] 는 dp[i-1], dp[i/3], dp[i/2] 중의 최솟값에 +1 (이 경우들에서 한 단계만 더 연산하면 답을 구할 수 있으므로) 를 더해주면 된다는 점에서 dp를 사용해서 푸는 문제임을 알 수 있다. 

 

우선 메모이제이션할 배열 dp를 선언해 준다. 여기서는 따로 함수를 만들지 않고 main함수 안에서 모두 해결하였으므로 배열의 크기를 N으로 선언한다. 

위에서 언급했듯이, dp[i] 의 최적해에는 3가지 경우가 존재한다. 

1. dp[i-1] + 1 (1을 뺄 수 있으므로)

2. dp[i/2] (2로 나눌 수 있으므로. i가 2로 나누어지는 경우에만 성립한다.)

2. dp[i/3] (3으로 나눌 수 있으므로. i가 3으로 나누어지는 경우에만 성립한다.)

 

이 세가지를 구현하고 최솟값을 구해 1을 더한 값을 dp[i]에 저장하는 것을 반복한다.

base case는 : dp[1]이다. 1은 그 자체로 답이므로 dp[1]는 0이다. 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int dp[N+1];
	
	for(int i=1; i<=N; i++){
		if (i==1) {
			dp[i] = 0;
		}
		else {
			vector <int> v;
			v.push_back(dp[i-1]);
			if (i%2 == 0) v.push_back(dp[i/2]);
			if (i%3 == 0) v.push_back(dp[i/3]);
			
			sort(v.begin(), v.end());
			dp[i] = v[0]+1;
		}
	}
	cout << dp[N];
}

 

우선 cin.tie(NULL); ios::sync_with_stdio(false); 를 선언해준다. (https://chocodingdiary.tistory.com/45)

그리고 N값을 먼저 받아준 뒤, 메모이제이션할 배열 dp를 선언해 주었다. i일 때의 값을 d[i]에 저장할 것이므로 N+1인 배열을 선언한다. 

	cin.tie(NULL); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int dp[N+1];

 

본격적으로 동적계획법 부분이다.

우선 base case, 즉 i=1일 때 0을 저장하도록 한다. 

	for(int i=1; i<=N; i++){
		if (i==1) {
			dp[i] = 0;
		}

 

그리고 앞서 말한 부분해 세가지를 모두 계산해 가능한 값을 임시 vector v에 저장해준다. 

		else {
			vector <int> v;
			v.push_back(dp[i-1]);
			if (i%2 == 0) v.push_back(dp[i/2]);
			if (i%3 == 0) v.push_back(dp[i/3]);

i가 2의 배수일 경우 dp[i/2]를, i가 3의 배수일 경우 dp[i/3]이 저장되도록 했다.

 

그리고 이 중의 최솟값을 구해 여기에 1을 더한 것을 dp[i]에 저장하였다. 

그리고 dp[N]을 출력하면 끝!

			sort(v.begin(), v.end());
			dp[i] = v[0]+1;
		}
	}
	cout << dp[N];
}