TIL day 79

1. 코딩테스트

---

오늘 오전에는 저번에 연습이 필요하다고 느껴진 배낭문제 유형의 DP 문제를 풀었습니다.

 

평범한 배낭

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

#include <iostream>
using namespace std;

int n, k;
pair<int, int> props[102];
int dp[102][100'002];
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
	{
		int w, v;
		cin >> w >> v;

		props[i].first = w;
		props[i].second = v;
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= k; ++j)
		{
			//넣을 수 있다면,
			if (j + props[i].first <= k)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + props[i].first] + props[i].second);
			else
				dp[i][j] = dp[i - 1][j];

			answer = max(answer, dp[i][j]);
		}
	}
	cout << answer;
}

 

동전

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

#include <iostream>
using namespace std;

int t;
int coins[22];
int dp[10002];

//n개의 동전으로 m 만들기
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;

	while (t--)
	{
		int n;
		int m;
		int answer = 0;

		cin >> n;

		fill(coins, coins + 22, 0);
		fill(dp, dp + 10002, 0);

		for (int i = 1; i <= n; ++i)
		{
			cin >> coins[i];
		}
		cin >> m;
		dp[0] = 1;

		for (int i = 1; i <= n; ++i)
		{
			for (int j = coins[i]; j <= m; ++j)
			{
				dp[j] += dp[j - coins[i]];
			}
		}
		cout << dp[m] << "\n";
	}

}

 

추가적으로 해당 유형에 대한 내용을 정리해 보았습니다.

https://gbleem.tistory.com/160

DP (배낭 문제)

 

 

2. 언리얼

---

프로젝트 진행 전, 서버 공격 동기화에 대한 내용을 공부하였습니다.

https://gbleem.tistory.com/158

Unreal Engine - 데디케이티드 서버 6 (동기화)