라이님 블로그 대회 알고리즘 따라잡기 13) DP2 이해하기

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220793134705&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

동적 계획법 2(Dynamic Programming 2) (수정: 2016-08-22)

 

※ 이번 포스팅에 모든 내용은 위 블로그에 있습니다! 정확한 내용을 위해 위 포스팅을 참고하세욥🪄

 

 

 

여기 나오는 내용이 어려워서 ㅠㅡㅠ 나를 위해 정리해보려고 한다!

 

1. 백준 1149번 RGB거리

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr int INF = 1000000000;

int N, cost[1000][3], dp[1001][4], choice[1001][4];

// 바로 이전 마을에 prev번 색이 칠해져 있을 때 pos~N-1번 마을을 색칠하는 최소비용
// (i != prev 중) RGB(0, prev = 3) = min_k(RGB(1, i) + cost[1][i]);

int RGB(int pos, int prev = 3) {
	int& ret = dp[pos][prev];
	if (ret != -1) return ret;
	if (pos == N) return ret = 0;

	ret = INF;
	for (int i = 0; i < 3; i++) {
		if (prev != i && ret > RGB(pos + 1, i) + cost[pos][i]) {
			ret = RGB(pos + 1, i) + cost[pos][i];
			choice[pos][prev] = i;
		}
	}
	return ret;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			scanf("%d", &cost[i][j]);
	memset(dp, -1, sizeof(dp));
	memset(choice, -1, sizeof(choice));
	printf("%d\n", RGB(0));
}

 

2. 백준 2533번 사회망 서비스(SNS)

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

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int INF = 10 ^ 9;

vector<int> adj[1000000], child[1000000];
bool visited[10000000];
int N, dp[1000000][2];
bool picked[1000000][2];

void dfs(int curr) {
	visited[curr] = true;
	for (int next : adj[curr]) {
		if (!visited[next]) {
			child[curr].push_back(next);
			dfs(next);
		}
	}
}

int SNS(int curr, bool pe) {
	int& ret = dp[curr][pe];
	if (ret != -1) return ret;

	int notpick = INF, pick = 1;
	for (int next : child[curr])
		pick += SNS(next, true);
	if (pe) {
		notpick = 0;
		for (int next : child[curr])
			notpick += SNS(next, false);
	}
	// picked = true : 얼리어답터
	picked[curr][pe] = (pick < notpick);
	return ret = min(notpick, pick);
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);

	memset(dp, -1, sizeof(dp));
	memset(picked, false, sizeof(picked));
	printf("%d\n", SNS(0, true));
}

 

3. 백준 2248번 이진수 찾기

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

 

nCr 계산과 똑같은 로직! 

근데 이걸 어떻게 코드로 잘 구현하는지 정말 멋지다..ㄷㄷ

덕분에 또 배워가는 중!!!!

 

#include <cstdio>
#include <cstring>
using namespace std;

int dp[32][32];
char result[32];

int binary(int n, int m) {
	int& ret = dp[n][m];
	if (ret != -1) return ret;
	if (m == 0 || n == 0) return ret = 1;
	
	// 첫 번째 비트를 0으로 선택한 경우, 나머지 n-1 비트에서 m개의 1을 선택
	ret = binary(n - 1, m);
	// 첫 번째 비트를 1로 선택한 경우, 나머지 n-1 비트에서 m-1개의 1을 선택
	if (m > 0) ret += binary(n - 1, m - 1);
	return ret;
}

void skip(int n, int m, int k, int p) {
	if (n == 0) return;
	if (m == 0) {
		for (int i = 0; i < n; i++)
			result[p + i] = '0';
		return;
	}

	int pivot = binary(n - 1, m);
	if (k < pivot) {
		result[p] = '0';
		skip(n - 1, m, k, p + 1);
	}
	else {
		result[p] = '1';
		skip(n - 1, m - 1, k - pivot, p + 1);
	}
}

int main() {
	int N, L;
	long long I;
	scanf("%d %d %lld", &N, &L, &I);
	memset(dp, -1, sizeof(dp));
	skip(N, L, I - 1, 0);
	puts(result);
}

출처 : https://github.com/kks227/BOJ/blob/master/2200/2248.cpp