이것이 코딩테스트다 - 8) 다이나믹 프로그래밍(다시 풀어보기)

 

 

 

 

 

 

정말 처참한 다이나믹 프로그래밍...

꼭 다시 봐야한다. 😭

 

 

 

 

8.1) 1로 만들기

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


using namespace std;

int x;
int dp[30001] = { 0, };

int main() {

	cin >> x;
	//dp[1]=0이므로 2부터 시작한다. (보텀업)
	for (int i = 2; i <= x; i++)
	{	//현재의 수에서 1을 빼는경우
		dp[i] = dp[i - 1] + 1;
		//현재의 수에서 2으로 나누는 경우
		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
		//현재의 수에서 3으로 나누는 경우
		if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
		//현재의 수에서 5로 나누는 경우
		if (i % 5 == 0) dp[i] = min(dp[i], dp[i / 5] + 1);
	}
	cout << dp[x] << endl;
}



/*
 처음에 했던 방식(실행 안된다)
int X, x, cnt =0;
int dp[30000] = { 0, };
int calculate(int X, int x, int cnt) {
	if (x == 1) {
		dp[X] = cnt;
		return cnt;
	}
	if (dp[x] != 0) {
		cnt += dp[x];
		dp[X] = cnt;
		return cnt;
	}
	if (x % 5 == 0) {
		x /= 5;
		cnt++;
	}
	else if (x % 3 == 0)
	{
		x /= 3;
		cnt++;
	}
	else if (x % 2 == 0) {
		x /= 2;
		cnt++;
	}
	else {
		x -= 1;
		cnt++;
	}
	calculate(X,x, cnt);
	return cnt;
}
int main() {
	cin >> X;
	int x = X;
	cout << calculate(X, x, 0) << endl;
}*/

 

 

 

 

8.2) 개미 전사

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


using namespace std;


int n;
vector<int> food;
int d[101];


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int k;
		cin >> k;

		food.push_back(k);
	}

	d[0] = food[0];
	d[1] = max(food[0], food[1]);

	//다이나믹 프로그래밍 (보텀업)
	for (int i = 2; i < food.size(); i++)
	{
		d[i] = max(d[i - 1], d[i - 2] + food[i]);
	}

	cout << d[n - 1] << endl;

}

 

 

 

 

 

 

8.3) 바닥 공사

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


using namespace std;

int d[1001];
int n;

int main() {
	cin >> n;

	d[0] = 0;
	d[1] = 1;
	d[2] = 3;

	//다이나믹프로그래밍(보텀업)
	for (int i = 3; i <= n; i++)
	{
		d[i] = (d[i - 1] + d[i - 2] * 2) % 796796;
	}

	cout << d[n] << endl;

	return 0;

}

 

 

 

 

8.4) 효율적인 화폐 구성

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


using namespace std;


int n, m;
vector<int> money;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int number;
		cin >> number;
		money.push_back(number);
	}
	vector<int>d(m + 1, 10001);

	//다이나믹 프로그래밍(보텀업)
	d[0] = 0;
	for (int i = 0; i < n; i++)//화폐단위마다 검색
	{
		for (int j = money[i]; j <= m; j++)//화폐단위의 값부터 구하려는 값까지 설정
		{
			//화폐단위로 계산이 되는 값은 10001값이 아닐 것이다. (i-k원이 존재하는 경우)
			if (d[j - money[i]] != 10001) {
				//방법이 생기고 값에 따라서 최솟값 계속해서 갱신
				d[j] = min(d[j], d[j - money[i]] + 1);
			}
		}
	}


	if (d[m] == 10001)//만드는 방법이 없는 경우
	{
		cout << "-1" << endl;
	}
	else { cout << d[m] << endl; }

	return 0;

}