이것 저것 &

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

문제를 보자마자 아이디어는 금방 떠올랐습니다.

문제조건에서 

• 편의상 자원은 무한히 많이 가지고 있고,
• 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다

하였으니 단순히 이전 건물을 짓는데 시간과 자신의 건축시간을 더한 값입니다.

dp[num]을 자신의 건물 완성 최소시간이라 할때

dp[num] = 자신의 건축시간 + max(선이수 건물 완성 최소시간) 입니다.

이때 구현방법을 고민해봐야 합니다.

일반적인 dp구현방식인 (down-up) 방식을 사용할 수 없습니다. 선이수 건물이 이미 완성 되었는지 모르기 때문입니다.

즉, 재귀호출방식(up-down)방식을 사용해야합니다. 이때 이미 구한 값은 비트마스킹 과정을 통해 값을 저장하고, 중복해서 계산하지 않는 것이 포인트 입니다.

아래는 정답코드입니다.

구조체 벡터때문에 복잡해보이지만 굉장히 간단한 논리입니다. 천천히 확인해 보세요!

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

typedef struct MyStruct
{
	int time;
	vector <int> prefer;

}val;
val arr[501];
int n;
int dp[501];

int solved(int num) {

	if (dp[num] != 0) return dp[num];


	int maxed = 0;
	for (int i = 0; i < arr[num].prefer.size(); i++) {
		maxed = max(maxed, solved(arr[num].prefer[i]));
	}
	dp[num] = maxed + arr[num].time;
	return dp[num];
}

int main() {

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

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i].time;
		int temp;
		while (1) {
			cin >> temp;
			if (temp == -1) {
				break;
			}
			arr[i].prefer.push_back(temp);
		}
	}
	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i].prefer.size() << endl;
	*/

	for (int i = 1; i <= n; i++)
		cout << solved(i) << endl;

	return 0;
}

재귀를 쓰지않고 bfs를 활용해서도 답을 얻을 수 있습니다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int degree[501] = { 0, };
int N, n;
vector<int> vec[501];
int time[501], result[501];

void bfs() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (degree[i] == 0) {
			q.push(i);
			result[i] = time[i];
		}
	}

	while (!q.empty()) {
		int front = q.front();
		q.pop();
		for (int i = 0; i < vec[front].size(); i++) {
			int e = vec[front][i];
			result[e] = max(result[e], result[front] + time[e]);
			if (--degree[e] == 0)
				q.push(e);
		}
		
	}
}


int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> n;
		time[i] = n;
		while (1) {
			cin >> n;
			if (n == -1)	break;
			vec[n].push_back(i);
			degree[i]++;
		}
	}
	bfs();
	for (int i = 1; i <= N; i++)
		cout << result[i] << "\n";
	return 0;
}

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

dp문제입니다. 점화식을 생각하는데 오래 걸렸습니다.

인접하게 칠할 수 없다는 조건이 있습니다.

dp[N][K] = N 개 짜리 색에서 K 개를 인접하지 않게 칠하는 경우의 수

점화식 : dp[n][k] = dp[n-2][k-1] + dp[n-1][k] 

표를 작성하면서 해당 점화식 규칙을 알게 되었습니다. 두개이상의 색을 구할때는 색칠한 경우와 하지 않은 경우로 구분하여 생각하면 됩니다. 

아래는 정답코드입니다.

#include <iostream>
using namespace std;

int dp[1001][1001] = { 0 };
int n = 0, k = 0;
int result = 0;

int main() {

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

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		dp[i][1] = i;
		for (int j = 2; j <= i / 2; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % 1000000003;
		}
	}
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 3; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	result = dp[n][k];
	cout << result << endl;

	return 0;
}

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

dp문제라기보다는 그리디 문제에 가까웠습니다. 

문제에서 주는 조건들입니다.

• 항상 선행작업부터 처리한다.
• 선행작업의 번호는 자신의 번호보다 작다.
• 선행작업이 아니라면 동시작업이 가능하다.

3가지 규칙에 의해서 1번작업부터 오름차순으로 작업시간을 정의내리면 결과값을 도출할 수 있습니다.

굳이 점화식으로 나타내자면,   dp[n] = current_time + max( 1~dp[n-1]) 일것입니다. 

그리고 이러한 값들중 가장 큰 값이 결과값이 되는 것입니다. 

문제의 원리를 이해하셨다면 구현자체는 전혀 어려움이 없으셨을겁니다.

아래는 정답코드입니다. 

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

int dp[10001] = { 0, };
int n;
int time = 0, cnt = 0, value = 0;
int result = 0;

int main(void) {

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> time >> cnt;
		if (cnt == 0) {
			dp[i] = time;
			continue;
		}
		int maxed = 0;
		for (int j = 0; j < cnt; j++) {
			cin >> value;
			maxed = max(maxed, dp[value]);
		}
		dp[i] = time + maxed;
	}
	/*
	for (int i = 1; i <= n; i++)
		cout << dp[i] << endl;
	*/


	for (int i = 1; i <= n; i++)
		result = max(result, dp[i]);

	cout << result << endl;


	return 0;
}

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

dp 문제였습니다.

우선 규칙성을 이해하기 위해 n과 m 개수에 따른 경우의 수를 생각해봤습니다.

즉 경우의 수는 dp[i][j] = dp[i][j-1] + dp[i-1][j] 입니다. 

이때 어떠한 규칙으로 az의 조합이 결정되는지 생각해보겠습니다.

ex) 2 2 2 일 경우

dp[2][2] = 6이고 dp[2][1], dp[1][2] = 3 이다. 2번째 문자열일 경우 첫문자는 a가 되고 dp[2][1]에 속하게 된다. 

dp[2][1]에서도 2번째 문자열이다. dp[1][1] = 2, dp[2][0] = 1 이므로 두번째 문자는 z가 되고 dp[1][1]에 속하게 된다.

이런 형태로 반복하면 azaz가 된다.

for(int i=0;i<n+m;i++) {
		int a_start = dp[a_cnt - 1][z_cnt];
		int z_start = dp[a_cnt][z_cnt - 1];

		//cout << a_start << endl;
		if (a_cnt == 0) {
			cout << 'z';
			z_cnt--;
			continue;
		}
		else if (z_cnt == 0) {
			cout << 'a';
			a_cnt--;
			continue;
		}

		if (k <= a_start) {
			cout << 'a';
			a_cnt--;
		}
		else {
			k = k - a_start;
			cout << 'z';
			z_cnt--;
		}


	}

위와 같은 형태로 진행해주면 된다.

한가지 조심해야할 점은 K는 1,000,000,000보다 작거나 같은 자연수라는 점이다. 나도 이 부분 때문에 꽤 애먹었다. 

k가 10억이기 때문에 n과 m의 경우의수 int형의 범위는 물론이고 long long의 범위를 쉽게 넘어가는 경우가 발생한다. 

이 때 오버플로우에 의해서 음수가 저장되며  경우의 수 값이 달라질 수 있기 때문에 1,000,000,000이 넘어가면 그냥 1,000,000,000을저장하여 문제를 해결하였다.  어차피 1,000,000,000번째 까지의 문자열을 확인해줄거기 때문에 값이 더 클 때 1,000,000,000이라고 저장하는게 유효한 것이다. 어차피 그러면 앞에 a인 것을 동일하기 때문이다.

이거를 이해하는데 오래 걸렸다. ㅠㅠ

정답코드입니다.

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



int n = 0, m = 0;
int k = 0;

long long dp[101][101];




int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;

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

	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			if (dp[i][j] > 1000000000) dp[i][j] = 1000000000;
		}
	
	int a_cnt = n;
	int z_cnt = m;
	if (dp[n][m] < k) {
		cout << -1 << endl;
		return 0;
	}
		
	for(int i=0;i<n+m;i++) {
		int a_start = dp[a_cnt - 1][z_cnt];
		int z_start = dp[a_cnt][z_cnt - 1];

		//cout << a_start << endl;
		if (a_cnt == 0) {
			cout << 'z';
			z_cnt--;
			continue;
		}
		else if (z_cnt == 0) {
			cout << 'a';
			a_cnt--;
			continue;
		}

		if (k <= a_start) {
			cout << 'a';
			a_cnt--;
		}
		else {
			k = k - a_start;
			cout << 'z';
			z_cnt--;
		}


	}

	cout << "\n";
	return 0;
}

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

쉬운 dp 문제였습니다.

조건은 두가지입니다. 

1. 수열에서 수를 하나 제거할 수 있다.

2. 제거하지 않아도 된다.

우선 제거하지 않을때는 

if (dp[i - 1][0] > 0)
dp[i][0] = arr[i] + dp[i - 1][0];
else
dp[i][0] = arr[i];

로 쉽게 구할 수 있습니다.

그리고 하나의 수를 제거할 때는 

1) 현재 자신을 제거한 값이 큰지,

2) 이전에 제거한 값 + 현재값이 큰지

비교합니다.

정답코드입니다.

너무 쉬워서 점화식은 따로 기재하지 않았습니다.

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

/* 
제거 한경우 제거 안한 경우 

10 -4  3 1 5 6  -35 12 21 -1

0: 10 6 9 10 15 21 -14 -2 19 18   
1: 0 10 13   
현재 자신에서 뺀값이라 이미 빠진값이랑 비교해서 더큰값으로 넣는다. 
*/

int dp[100001][2] = { 0 };
int arr[100001] = { 0 };
int n = 0, result = -1000000000;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	dp[1][0] = arr[1];

	for (int i = 2; i <= n; i++) {
		if (dp[i - 1][0] > 0)
			dp[i][0] = arr[i] + dp[i - 1][0];
		else
			dp[i][0] = arr[i];
	}
	
	dp[1][1] = 0;

	for (int i = 2; i <= n; i++) {
		//1. 자신을 제외했을때 값과 이미 제한값을 비교
		int a = dp[i - 1][0]; //자신을 제외했을때
		int b = dp[i - 1][1] + arr[i];
		dp[i][1] = max(a, b);
	}

	for (int i = 2; i <= n; i++) {
		if (result < dp[i][0]) result = dp[i][0];
		if (result < dp[i][1])	result = dp[i][1];
	}
	if (result < dp[1][0]) result = dp[1][0];




	if (n == 1) cout << arr[1] << endl;
	else cout << result << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/2688

전형적인 dp문제입니다. 이전단의 결과값들이 현재 결과값에 영향을 미치기 때문입니다. 

예를 들어 n = 1일때 0 1 2 3 ~~ 9 로 총 10가지 경우의 수입니다.

n=2 일때  

0으로 시작할때  0~9 로 10개

1로 시작할때 1~9로 9개

2로 시작할때 2~9로 8개

3로 시작할때 3~9로 7개

.

.

.

9로 시작할때 9~9로 1개

즉

for (int k = j; k <= 9; k++)
      dp[i][j] += dp[i - 1][k]; 

와 같은 점화식을 가지게 됩니다.

정답코드입니다. 

#include <iostream>
using namespace std;

long long dp[65][10] = { 0 };
int t = 0, n = 0;

int main() {

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

	for (int i = 2; i <= 64; i++) 
		for (int j = 0; j <= 9; j++) 
			for (int k = j; k <= 9; k++)
				dp[i][j] += dp[i - 1][k];
		
	cin >> t;
	while (t--) {
		cin >> n;
		long long result = 0;
		for (int i = 0; i <= 9; i++)
			result += dp[n][i];
		cout << result << '\n';
	}
}

문제링크:https://www.acmicpc.net/problem/11049

11066번 파일합치기와 짝궁인 문제 입니다.

dp 문제이고 두가지 푸는 방식이 있습니다.

• 1. down-up 방식 ->  대각선 dp 라는 방법을 통해서 삼중포문을 통해서 구현하는 방법입니다. 시간이 빠릅니다.
• 2. up-down 방식 -> 재귀를 통해서 아래의 dp값들을 구하고 최종 결과값을 구하는 형태입니다. 직관적인 것이 장점입니다. 

점화식을 유추해야합니다. 우선은 dp[i][j]는 i부터 j까지의 곱셈연산의 최소값이라고 가정합시다.

이때 dp[1][1] = 0이고 dp[1][2] = 5 * 3 * 2가 됩니다.

입력이 

4

5 3

3 2

2 6

6 4

일때 표로 나타내면 

dp[1][3] 일때 5*3*2 + 5*2*6 = 90이 3*2*6 + 5*3*6보다 작기 때문에 90이 됩니다.

이처럼 이전 dp값들을 통해 비교하며 결과를 도출해야합니다. 

점화식은 dp[i][j] = dp[i][k] + dp[k+1][j] + arr[i][0]*arr[k][1]*arr[j][1] 입니다. ( k는 i부터 j까지 반복)

모든 지점에서 값을 비교해주어야 하기때문에 i부터 j 까지 k값을 반복해주어야 하는 것입니다.

dp[i][j] 는 dp[i][k] 구간과 dp [k+1][j] 의 합에다가 두 부분을 잇는 arr[i][0]*arr[k][1]*arr[j][1] 의 합입니다. 

저는 up-down 방식으로 문제를 해결했습니다.

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

int n = 0;
int arr[501][2];
int dp[501][501];

int  sol(int st,int ed) {
	if (st == ed) return dp[st][ed] = 0;
	if (st + 1 == ed) return dp[st][ed] = arr[st][0] * arr[st][1] * arr[ed][1];

	int &ret = dp[st][ed];

	if (ret != -1)
		return ret;

	for (int i = st; i < ed; i++) {
		int temp = sol(st, i) + sol(i + 1, ed) + arr[st][0] * arr[i][1] * arr[ed][1];
		if (ret > temp || ret == -1) ret = temp;
	}

	return ret;
}


int main() {
	cin >> n;

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

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


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

문제를 풀면서 아직 많이 부족하다는 것을 느꼈습니다. 

더 노력하겠습니다.

-----추가----

점화식에 대해서 많이 고민해봤습니다.

for (int i = st; i < ed; i++) {
		int temp = sol(st, i) + sol(i + 1, ed) + arr[st][0] * arr[i][1] * arr[ed][1];
		if (ret > temp || ret == -1) ret = temp;
	}

처음 sol(1,3) 이라면,

dp[1][3] = min(sol(1,1) + sol(2,3) + arr[1][0] + arr[1][1](arr[2][0]) + arr[3][1], 자기자신)

dp[1][3] = min(sol(2,1) + sol(3,3) + arr[1][0] + arr[2][1](arr[3][0]) + arr[3][1], 자기자신)

이 규칙대로 변화가 일어나는데, dp[i][j]가 i부터j까지의 최소값이기 때문입니다. 

문제링크:https://www.acmicpc.net/problem/11066

어려웠습니다.

처음에 문제의 조건을 잘못 읽고 순서가 바뀌어도 되는줄 알고 그리디적인 관점으로 생각했다가 틀렸습니다. 

dp적인 관점으로 생각해야하는 문제입니다. 예시인 40 30 30 50을 봅시다. 

아래의 표는 i부터 j까지의 합의 최소값을 나타내는 표입니다. 

즉 각각의 값들은 min(기존값,  좌와 아래로 내려간 값들의 합 + 대각선 횟수만큼 sum 값의 차이) 입니다. 

3중 포문을 통해서 구현해야 합니다.

코드는 먼저 보여드리겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//(int)2e9;
int sum[501] = { 0 };
int arr[501] = { 0, };
int dp[501][501] = { 0, };
int t = 0, k = 0;
int result = 0;
int main() {
	cin >> t;

	while (t--) {
		cin >> k;
		result = 0;
		for (int i = 1; i <= k; i++) {
			cin >> arr[i];
			sum[i] = sum[i - 1] + arr[i]; 
		}
		
		for (int i = 1; i < k ; i++) { // 1부터~ k-1 까지 반복 대각선의 개수
			for (int j = 1; j + i <= k; j++) { //  행을 나타낼 j변수   
				int v = j + i;    //  열값을 표현 
				dp[j][v] = (int)2e9;  // 2*10^9

				for (int u = j; u < j + i; u++) // 점 기준으로 좌와 하로 내려가면서 값 비교하기 위한 반복분 j부터 i번 반복
					dp[j][v] = min(dp[j][v], dp[j][u] + dp[u + 1][v] + sum[j + i] - sum[j - 1]);
					//지정된 위치 값은 -> min(기존값,  좌와 아래로 내려간 값들의 합 + i만큼의 sum 값의 차이)
			}

		}
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= k; j++)
				cout << dp[i][j] << ' ';
			cout << endl;
		}
		cout << dp[1][k] << endl;

	}
	return 0;
}

삼중 포문을 통해서 구현하게 됩니다.

• 1. 첫번째 포문은 대각선의 수만큼 반복되게
• 2. 두번째 포문은 각 대각선마다 해당하는 개수만큼 반복되게 (i+j <= k)
• 3. 세번째 포문은 각 점마다 아래와 왼쪽으로 한칸씩 이동하며 반복되도록 

다음은 top-down 방식인 재귀를 통해서 구현한 코드입니다. 

점화식만 구하면 훨씬 직관적이고 빠르게 구현이 가능하지만 효율측면에서는 down-top 방식보다 느리다는 단점도 있습니다. 

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


int t, k;
int arr[501] = { 0, };
int dp[501][501] = { 0, };

int solved(int s, int e) {
	if (s == e) return 0;
	else if (s + 1 == e) return arr[e] - arr[e - 2];

	int &ret = dp[s][e];
	if (ret != -1)
		return ret;
	ret = 1000000000;
	for (int i = s; i <= e; i++) {
		ret = min(ret, solved(s, i) + solved(i + 1, e) + arr[e] - arr[s-1]);
	}
	return ret;
}

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

	cin >> t;
	while (t--) {
		memset(dp, -1, sizeof(dp));
		cin >> k;
		for (int i = 1; i <= k; i++) {
			cin >> arr[i];
			arr[i] = arr[i] + arr[i - 1];
		}

		cout << solved(1,k) << "\n";

	}


	

	return 0;
}

아래 문제를 풀어보면서 복습해봅시다.

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