이것 저것 &

문제링크:www.acmicpc.net/problem/4811

우선 규칙성을 찾으려고 노력했습니다. 그런데 규칙을 못찾았고, 자연스레 재귀함수를 사용한 dp인 up-down 방식으로 생각했습니다.

문제에서 주어지는 조건처럼 전체 알약, 반쪽 짜리 알약으로 구분하여 

dp[i][j]은 하나짜리 알약 i개가 있고 반쪽 짜리 알약 j개가 있을때 최대 경우의 수를 나타냅니다.

아래는 재귀함수 코드입니다.

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}

만약 whole =0 이면 half만 남은 상태니까 결과값은 1!

그리고 모든 경우에서 whole -1 , half +1  호출

만약 half가 있다면 whole,half-1도 호출후 더하기

아래는 정답코드입니다.

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


long long dp[31][31];

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	for (int i = 1; i <= 1001; i++) {
		memset(dp, -1, sizeof(dp));
		int temp;
		cin >> temp;
		if (temp == 0)
			break;
		cout << solved(temp, 0) << "\n";
	}

	return 0;
}

문제링크:www.acmicpc.net/problem/2533

어려웠습니다..ㅠㅠ

dp(up-down) 문제인건 인식했지만 우선 그래프를 어떤식으로 구현하고 dp를 구현할지 설계를 하는데 어려움을 겪었습니다.

• 1. 단방향 그래프 만들기
• 2. 그래프를 탐색하며 최소수 구하기

1. 우선 입력 받을때는 양방향으로 받고 재귀함수를 통해서 결과를 도출합니다.

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

parent 벡터에만 child 노드들을 넣어 놓음으로서 단방향 트리를 구현했습니다.

2. 그래프를 탐색하며 최소수 구하기는 일반적인 dp(up-down)과 흡사합니다. 

if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

 1) 현재 노드가  얼리 어뎁터일때는 자식노드가  얼리 어뎁터일수도, 아닐수도 있습니다.

 2) 하지만 현재 노드가 얼리어뎁터가 아니라면  무조건 다음 노드는 얼리 어뎁터이어야 합니다.

2가지 조건을 통해서 재귀를 구현했습니다. 

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


int n = 0;
vector <int> vec[1000001];
vector <int> graph[1000001];
int dp[1000001][2] = { 0, };

int solved(int current, bool adapter) {
	if (graph[current].empty()) {
		if (adapter)
			return 1;
		else
			return 0;
	}
	
	int &ret = dp[current][adapter];
	if (ret != -1)
		return ret;

	if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

	return ret;

}

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

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

	cin >> n;
	for (int i = 0; i < n -1 ; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	make_graph(1, 0);
	/*
	for (int i = 0; i < n; i++) {
		cout << graph[i].size() << endl;
	}*/

	memset(dp, -1, sizeof(dp));
	cout << min(solved(1, 0), solved(1, 1)) << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/18427

무난한 난이도의 dp 문제였습니다.

한 학생당 최대 1개의 블록라는 조건을 통해서 배낭문제 알고리즘으로 해결할 수 있습니다.

dp[i][j] 는 i번째까지 학생에게 j높이에서의 최대 경우의수라고 할때, 아래와 같이 됩니다. (초기화 작업으로 0일때는 1로 지정)

첫번째 학생이 2,3,5니까, dp[1]은 101101이 되고 두번째 학생을 포함하면 101203이되고... 

그러면 학생이 가진 블록뺀 dp[i-1][j-vec[i][k]] 만큼씩 더해주고 그 이후에 dp[i-1][j] 을 더해주면 해결됩니다.

조심할 점은  if (j >= vec[i][k]) 일때 dp[i - 1][j - vec[i][k]]을 수행하여야 한다는 점이다. 

아래는 정답코드입니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n, m, h;
vector <int> vec[51];
int dp[51][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> h;
	cin.ignore(1);

	for (int i = 1; i <= n; i++) {
		string temp;
		getline(cin, temp, '\n');
		
		for(int j=0;j<temp.size();j++)
			if(temp[j]==' '||j==0)
				vec[i].push_back(stoi(&temp[j]));

			
	}
	

	
	//solve

	for (int i = 0; i <= n; i++)
		dp[i][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= h; j++) {
			
			
			for (int k = 0; k < vec[i].size(); k++) {
				
				if (j >= vec[i][k]) {
					dp[i][j] += dp[i - 1][j - vec[i][k]];
					dp[i][j] %= 10007;
				}
			}		
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}


	cout << dp[n][h] << endl;


	return 0;
}

문제링크: www.acmicpc.net/problem/2616

down-up방식 점화식을 구하지 못해 up-down 방식을 사용했습니다.

한점 기준으로 해당 위치부터 소형 기관차를 사용하는 경우 혹은 사용하지 않는 경우 두가지를 비교해주며 결과값을 도출했습니다.

dp[i][j]는 i번째 위치에서부터  j개의 소형기관차를 사용할때 얻을 수 있는 최대값을 가르킵니다. 이때 점화식은

• max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1])); 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n = 0, k = 0;
int dp[50001][3] = { 0, };
int arr[50001] = { 0, };

int solved(int current, int cnt) {

	if (current > n || cnt == 3)
		return 0;

	int &ret = dp[current][cnt];
	if (ret != -1)
		return ret;

	if ((current + k - 1) <= n)
		ret = max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1]));


	return ret;
}



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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int temp = 0;
		cin >> temp;
		arr[i] = arr[i - 1] + temp;
	}
	cin >> k;
	memset(dp, -1, sizeof(dp));
	cout << solved(1, 0) << endl;

	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i] << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	return 0;
}

down-up방식도 가능할거 같아 찾아봤습니다.

lyzqm.blogspot.com/2017/03/2616.html

DP[N][M]=max(DP[N][M−1],DP[N−1][M−K]+S[M]−S[M−K] 해당 점화식 사용하셔서 푸는 답도 있습니다. 

문제링크:www.acmicpc.net/problem/17208

냅색알고리즘을 아는냐 모르냐에 따라서 체감 난이도가 큰 문제입니다.

우선 배낭여행 알고리즘을 모른다 하시면 아래링크 문제부터 풀어 보세요.

gusdnr69.tistory.com/153 

평범한 배낭문제와 같은 맥락입니다.

하지만 감튀랑 버거 두가지를 함께 고려해주어야 하는 문제입니다.

저는 삼차원 배열을 만들어서 해결했습니다.

dp[i][j][u]  => n번째 손님까지, j개의 버거, u개의 감튀로 최대 몇명의 손님을 받을 수 있는가?

이를 위해서는 삼중 포문을 사용해야 합니다.

//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	

평범한 배낭문제와 굉장히 유사합니다.

아래는 전체 정답 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;

int dp[101][301][301] = { 0, };
int b[301] = { 0, };
int p[301] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) 
		cin >> b[i] >> p[i];

	//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	
	cout << dp[n][m][k] << endl;
}

손에 안 익으시다면 배낭여행 알고리즘 문제를 3~4개 푸시면서 다른 문제가 나와도 적용할 수 있게 연습해보세요.

문제링크:www.acmicpc.net/problem/7579

배낭문제 알고리즘으로 해결하는 문제입니다.

근데 기존 배낭문제에서는 배낭에 넣을 수 있는 최대값을 구하잖아요?

근데 이문제는 최소 값을 구해야 하고 무게가 아닌 시간값을 구해야하는게 다른 문제입니다. 

그래서 시간과 무게를 반대로 생각해서 점화식을 구현하는 문제입니다.

이 문제가 어려우시다면 아래 문제를 먼저 풀어보세요.

gusdnr69.tistory.com/153 

m[] 메모리 배열

c[]  비용 배열

dp[i][j]  i는 n개의 앱 중에서 몇번째 앱까지인지   j는 시간을 의미합니다.

이때 dp에 저장되는 값은 메모리값이 저장됩니다.

점화식은

if(j >= c[i])  dp[i][j] = max(dp[i-1][j], dp[i -1][j- c[i]] +m[i])

else dp[i][j] = dp[i-1][j] 

입니다.

dp[i][j] >= M 일때  min(result,j)를 통해서 결과값을 도출합니다.

아래는 정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int m[101] = { 0, };
int c[101] = { 0, };
int dp[101][10001] = { 0, };
int result = 1000000000;


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++){
		cin >> m[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> c[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 10000; j++) {
			if (c[i] <= j)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i]);
			else
				dp[i][j] = dp[i - 1][j];

			if (dp[i][j] >= M) result = min(result, j);
		}
	}
	

	cout << result << endl;

	return 0;
}

문제링크: www.acmicpc.net/problem/12865

제목 그대로 평범한 배낭문제 (knapsack) 입니다. 

배낭 문제는 

• 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)
• 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)

두가지로 분류됩니다.

 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로

그리디 알고리즘을 사용합니다.

물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법을 사용합니다.

해당문제는 dp를 사용하는 방식입니다.

전제조건

n은 물건개수, k는 가져갈 수 있는 무게값

w[]는 물건에 대한 무게값들

v[]는 해당 물건에 대한 가치값

i는 i번째 물건 j는 무게를 나타냅니다. 

즉, dp[i][j]는 i번째 물건까지 최대 j무게까지 가능할때 최고의 가치값입니다. 

점화식은

if(w[i]<=j) 일때는

dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j]

else

dp[i][j] = dp[i - 1][j]

이 됩니다.

이해가 가지 않으신다면 직접 표로 작성해보세요.

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;


int n, k;
int w[100001] = { 0, };
int v[1001] = { 0, };
int dp[101][100001] = { 0, };

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 1; i <= n; i++) 
		cin >> w[i] >> v[i];
	
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= k; j++) {
			if (w[i] <= j) {
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			}
			else
				dp[i][j] = dp[i - 1][j];
		}
	cout << dp[n][k] << endl;


	return 0;
}

심화문제는 7579번 앱!

좌측 검색누르셔서 제가 푼 코드 확인하실수 있습니다.

문제링크:www.acmicpc.net/problem/11062

근우와 명우가 돌아가면서 최선의 선택을 한다.

처음에 규칙성을 찾아보려고 했지만, 규칙성을 찾지를 못했습니다.

1 8 100 2 10 이나 1 8 10 200 10 와 같은 다양한 경우에 따라서 예외가 발생하기 때문에 규칙성이 아닌

모든 경우를 생각해보는 것으로 생각을 바꿨습니다.

근데 모든 경우를 항상 계산해주는것이 아니라 이미 계산한 내용이라면 비트마스킹을 통해 저장해두었다가 다시 전달하는 형태로 구현하는 것이 핵심입니다. 

dp[1001][1001][2] ->   앞에 두 1001은 1~1000까지 시작점, 끝점을 나타냅니다. 그리고 마지막 2는 0일때는 근우 1일때는 명우의 턴을 가르킵니다. 

재귀함수 호출 코드입니다. DP up-down 방식 

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}

turn이 0일때는 근우 1일때는 명우의 차례입니다. 이 과정을 통해서 최종 결과값을 도출합니다. 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


int dp[1001][1001][2];
int t,n;
int arr[1001];

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}


int main() {
	cin >> t;



	while (t--) {
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> arr[i];

		memset(dp, -1, sizeof(dp));

		
		cout << solved(1, n, 0)<<endl;// 0 is 근우 , 1 is 명우
		
	}


}