TIL day 77

1. 코딩테스트

---

오늘은 수업중에 DP관련 문제를 풀었습니다.

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

DP 배낭문제 유형의 문제였는데, 이 문제 유형 관련해서 좀 더 공부를 해봐야겠다는 생각이 들었습니다.

• 현재 턴을 가지고 진행하면서
• 체력과 같은 제한이 있는 경우
• 2차원 배열을 사용하고 2중 for문을 통해서 문제를 해결하는 것 같은데, 좀 더 템플릿화해서 익숙해져야 할 것 같습니다.

#include <iostream>
using namespace std;

int n;
pair<int, int> board[22];
int dp[22][102]; //현재 i번째 왔을때 남은 체력 j 일때의 기쁨
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> board[i].first; //체력
	}
	for (int i = 1; i <= n; ++i)
	{
		cin >> board[i].second; //기쁨
	}
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 100; j >= 0; --j)
		{
			if (j - board[i].first > 0)
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - board[i].first] + board[i].second);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
			answer = max(answer, dp[i][j]);
		}
	}

	cout << answer;
}

 

 

2. 언리얼

---

hmm...