이것 저것 &

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

우선순위 큐를 사용하여서 해결하는 문제

접근방식

1.  절댓값에 대한 순서를 우선순위 큐를 활용하여 해결하자!

문제풀이 

1.  pair형태의 우선순위 큐 생성

2. min-heap형태로 구성!

근데, "절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력" 하라는 조건이 있으니 두번째 원소값을 변형 하여서 구현하기

정답코드

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

priority_queue <pair<int, int>> que;
int n = 0;
int num = 0;

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

	cin >> n;
	while (n--) {
		cin >> num;
		if (num == 0) {
			if (que.size() == 0)
				cout << 0 << "\n";
			else {
				cout <<  que.top().first * que.top().second  << "\n";
				que.pop();
			}
		}
		else {
			if(num > 0)
				que.push(make_pair(-1 * abs(num),-1));
			else
				que.push(make_pair(-1 * abs(num), 1));
		}

	}

	return 0;
}

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

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  모든 좌표에서 도달 가능한 좌표를 탐색

이때, dp에 값을 저장해두었다가 같은 좌표를 탐색할때는 곧바로 반환해주는 형태로 구현

정답코드

#include <iostream>

using namespace std;

int n, m;
char arr[3001][3001];
long long dp[3001][3001];
long long result = 0;

long long solved(int y, int x) {
	if (y == n && x == m)
		return 1;

	long long& ret = dp[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (arr[y][x] == 'B') {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else if (arr[y][x] == 'E') {
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
	}

	ret %= 1000000009;

	return ret;
}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			result += solved(i, j);

	cout << result % 1000000009 << endl;

	return 0;
}

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

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  높이 수면에 닿는 경우는 항상 배제시켜주고, 

시간이 다 될때 까지 수면에 닿지 않았다면 + 1 을 추가해주는 형태로 진행함

정답코드

#include <iostream>
using namespace std;

long long dp[64 * 2][64];
int n, k;

long long solved(int kk, int nn) {
	
	if (kk == 0)
		return 0;
	if (nn == 0)
		return 1;

	long long& ret = dp[kk][nn];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(kk-1, nn-1);
	ret += solved(kk+1, nn-1);

	return ret;
}

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

	cin >> k >> n;

	for (int i = 0; i < 64*2; i++)
		for (int j = 0; j < 64; j++)
			dp[i][j] = -1;

	cout << solved(k, n) << endl;

	return 0;
}

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

Top-down 방식의 dp로 해결했습니다. 

접근방식

1. 문제를 보면서 일반적인 dfs로는 구현이 불가능한 것을 이해하였고, dp로 구현하기로 함

2.  top-down방식을 통해서 구현

문제풀이 

1.  일반적인 top-down방식으로 구현 

주의점은 숫자 범위때문에 long long으로 선언해야한다는점?

아래는 정답 코드

#include <iostream>
using namespace std;
int t;
int n, m;
long long dp[2001][11];

long long solved(int currentN, int currentM) {

	if (currentN == 1)
		return 1;

	long long& ret = dp[currentM][currentN];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = currentM/2; i >= 1; i--) {
		ret += solved(currentN - 1, i);
	}

	return ret;
}

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

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

		for (int i = 1; i <= 2000; i++)
			for (int j = 1; j <= 10; j++)
				dp[i][j] = -1;

		long long result = 0;
		for (int i = m; i >= 1; i--)
			result += solved(n, i);

		cout << result  << "\n";

	}


	return 0;
}

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

top-down방식의 dp를 사용해서 해결하는 문제였습니다.

문제 예시에서는 k가 1이라 break는 총 3가지 경우가 포함이 됩니다.

모든 그래프에 대해서 단순 dfs나 bfs로는 시간문제때문에 해결을 할 수 없습니다.

dp를 통해서 탐색했던 내용을 복사해두고 다음번 탐색에서 사용할 수 있도록 구현해야 합니다.

접근방식

1. 그래프 탐색을 통해서 문제를 해결하자.

2. 속도적인 문제 때문에 dp를 통해서 문제를 해결하자.

문제풀이 

1. dp[100][100][81]로 생성 좌표와 몇번째 단어인지를 나타내는 인덱스들이다.

2. k가 늘어남에 따라서 이동할 수 있는 칸이 늘어나는데, while문을 사용해서 이러한 문제를 해결했다.

아래는 정답 코드

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

int dp[100][100][81]; // 0 base
char arr[100][100];
string word;

int n, m, k;

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

int result = 0;

int solved(int y, int x, int cnt) {

	
	if (cnt == word.size())
		return 1;

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

	ret = 0;

	for (int i = 0; i < 4; i++) {
		int  c = k;
		int ny = y;
		int nx = x;
		while (c--) {
			ny +=  y_ar[i];
			nx +=  x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (arr[ny][nx] != word[cnt])
				continue;
			ret += solved(ny, nx, cnt + 1);
		}
	}

	return ret;
}

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

	cin >> n >> m >> k;

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

	cin >> word;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int u = 0; u <= word.size(); u++)
				dp[i][j][u] = -1;



	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == word[0]) {
				result += solved(i, j, 1);
			}


	cout << result << endl;

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

	return 0;
}

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

dp문제입니다.

접근방식

1. 당연히 일반적인 방법으로 매번 검사하는건 불가능하다. 

O(n x m) => 2000 X  1,000,000 으로 가뿐히 10초를 넘기기 때문에

2. dp방식을 통해서 이미 검사해준 값이라면 또 탐색하지 말고 바로 값을 얻어오자

문제풀이 

1. top-down방식으로 dp[시작점][끝점]마다 가능한지 불가능한지 체크해주면서 넘어가자

2. 양 옆으로 한칸씩 줄이면서 탐색하는 구조 자세한 설명은 코드로

정답 코드

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

int n = 0, m = 0, st = 0, en = 0;
int arr[2000] = { 0, };
int dp[2000][2000];

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

	int& ret = dp[s][e];
	if (ret != -1) return ret;

	if (arr[s] == arr[e])
		ret = solved(s + 1, e - 1);
	else
		ret = 0;

	return ret;
}

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d", &arr[i]);
	
	for (int i = 0; i < 2000; i++)
		for(int j=0; j < 2000; j++)
			dp[i][j] = -1;

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &st,&en);
		printf("%d\n", solved(st - 1, en - 1));
	}


	return 0;
}

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

dp문제입니다.

접근방식

1. 모든 경우의 수를 고려하는 브루트 포스방식은 불가

2. 배낭 알고리즘처럼 n = 1 일때 부터 하나씩 경우의 수를 추가해주는 방식으로 구현 

3. 경우의 수에 대한 갯수가 아니라 단순히 가능, 불가능 여부이기 때문에 직관적으로 구현

문제풀이 

1. n개만큼 반복하며 i개까지 가지고 있을 때 분배가 가능한지 탐색

j를 top-down방식으로 사용하는 이유는 if문에서 이전 인덱스의 dp값을 참조하며 진행하기 때문이다. 

정답 코드

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

int dp[50001] = { 0, }, n = 0;
int won, cnt;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 3;
	
	while (t--) {
		int sum = 0;
		vector <pair<int, int>> vec;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> won >> cnt;
			vec.push_back(make_pair(won, cnt));
			sum += won * cnt;
		}
		if (sum % 2 == 1) {
			cout << 0 << endl;
			continue;
		}
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int i=0;i<n;i++)
			for (int j = 50000; j >= vec[i].first; j--) {
				if (dp[j - vec[i].first] == 1) {
					for (int k = 0; k < vec[i].second && (j + k*vec[i].first) <= 50000; k++) {
						dp[j + k*vec[i].first] = 1;
					}
				}
			}

		if (dp[sum / 2] == 1) {
			cout << 1 << endl;
		}
		else
			cout << 0 << endl;

	}


	return 0;
}

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

서브트리들의 정점 갯수를 구하는 문제

부모 노드의 경우 탐색을 해주면 안되는데,

이러한 문제를 메모이제이션을 통해서 문제를 해결할 수 있습니다.

아래는 정답 코드입니다.

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

vector <int> vec[100001];
int n, r, q;
int dp[100001];

int dfs(int n) {
	if (dp[n] != -1)
		return dp[n];
	
	int& ret = dp[n];	
	ret = 1;
	for (int i = 0; i < vec[n].size(); i++) {
		int next = vec[n][i];
		if (dp[next]!= -1)
			continue;
		ret += dfs(next);
	}
	
	return ret;
}

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

	cin >> n >> r >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		dp[i] = -1;
	dp[r] = dfs(r);
	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		cout << dp[c] << "\n";
	}


	return 0;
}