Week5

DP 문제풀이 예시(백준 1463번)

• Optimal Substructure
  X를 1로 만드는 방법은 X-1, X/2, X/3을 1로 만든 방법을 이용하여 구할 수 있습니다.

• Overlapping Subproblem
  X는 X+1, 2X, 3X를 계산할 때 사용됩니다. 즉 어떤 정수 X는 최대 3번 계산 되어야합니다.

위 두가지를 만족하므로 DP를 사용할 수 있습니다.

Top-Down 풀이

#include <bits/stdc++.h>

using namespace std;

int memo[1000001];

int go(int x) {
	if (x == 1)
		return 0;

	int& res = memo[x];

	if (~res)
		return res;

	res = 1e9;

	if (x % 3 == 0) {
		res = min(res, go(x / 3) + 1);
	}
	if (x % 2 == 0) {
		res = min(res, go(x / 2) + 1);
	}

	return res = min(res, go(x - 1) + 1);
}

int main() {
	int n;

	scanf_s("%d", &n);
	memset(memo, -1, sizeof(memo));

	printf("%d", go(n));

	return 0;
}

Bottom-Up 풀이

#include <bits/stdc++.h>

using namespace std;

int memo[1000001];

int main() {
	int n;
	scanf_s("%d", &n);

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

	printf("%d", memo[n]);

	return 0;
}

Plus) BFS 풀이

#include <bits/stdc++.h>

using namespace std;

int memo[1000001];

int main() {
	int n;

	scanf_s("%d", &n);

	queue<int> q;
	q.push(n);
	memo[n] = 1;

	while (q.size()) {
		int front = q.front();
		q.pop();

		if (front == 1) {
			printf("%d", memo[front] - 1);
			return 0;
		}

		vector<int> next;
		if (front % 3 == 0)
			next.push_back(front / 3);
		if (front % 2 == 0)
			next.push_back(front / 2);
		next.push_back(front - 1);

		for (auto element : next) {
			if (!memo[element]) {
				memo[element] = memo[front] + 1;
				q.push(element);
			}
		}
	}

	return 0;
}

(저는 개인적으로 아직 DP가 낯설고 어려워서 그런지 BFS풀이가 훨씬 친숙하고 이해하기 편했습니다 ㅇ.ㅇ)

Greedy

Greedy Algorithm은 탐욕법을 뜻합니다. 이 탐욕법은 매 순간 최적해를 구해나감으로써써 전체 문제의 최적해를 구해나가는 접근 방식입니다. 탐욕법은 반드시 이전 단계의 선택에 의해 현재 단계의 답이 영향을 받으면 안됩니다. 이 Greedy Algorithm은 코딩테스트 이외에도 실생활에 매우 실용적으로 사용될 수 있다고 합니다.( ex) 거스름돈 돌려줄 때, 저희는 무의식적으로 동전을 가장 적게 주는 방법으로 거슬러주곤 합니다. 이러한 방식 또한 어떻게 보면 Greedy Algorithm이 실생활에 적용된 예입니다.)

예제 문제(백준 11047번) 풀이

평소에 거스름돈을 어떤 방식으로 받는 지 생각을 먼저해봅니다. 보통 거스름돈 금액 내에서 가장 큰 금액들 위주로 생각하여 동전의 갯수를 줄일 것 입니다. 해당 문제도 가장 큰 금액의 동전부터 차례로 주는 방식으로 해결할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, k;
	scanf_s("%d %d", &n, &k);
	vector<int> v(n);

	for (int i = 0; i < n; i++)
		scanf_s("%d", &v[i]);

	reverse(v.begin(), v.end());
	
	int ans = 0;
	int i = 0;

	while (i < n && k) {
		ans += k / v[i];
		k %= v[i];
		i++;
	}

	printf("%d", ans);

	return 0;
}