이것 저것 &

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

해당 문제는 lcs와 연관이 있다.

LCS의 갯수를 통해서 팰린드롬을 위한 갯수 도출할수 있기 때문입니다.

논리자체는 굉장히 간단하다.

• 1. 입력받은 문자열과 문자열을 뒤집은 것과의 lcs 구하기
• 2. N - LCS 이 정답

우선 lcs는 아래 링크를 통해서 이해하자

gusdnr69.tistory.com/192

아래는 정답코드이다.

팰린드롬이 LCS와 연관이 있다는 것을 이해하는 것이 어려운 문제이고, 

구현 난이도는 매우 낮은 문제이다.

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

int n = 0;
string arr;
string arr_re;
int dp[5001][5001] = { 0, };

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

	cin >> n;
	cin >> arr;
	arr_re = arr;
	reverse(arr_re.begin(), arr_re.end());
	for (int i = 0; i < n; i++) {
		if (arr_re[0] == arr[i]) dp[0][i] = 1;
		else if(dp[0][i - 1] == 1)dp[0][i] = 1;

		if (arr_re[i] == arr[0]) dp[i][0] = 1;
		else if (dp[i - 1][0] == 1)dp[i][0] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_re[i] == arr[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}*/

	cout << n - dp[n - 1][n - 1] << endl;


	return 0;
}

문제풀이:www.acmicpc.net/problem/1577

특이한 dp 문제입니다. 

일반적으로 0,0에서 n,m으로 이동할때 2방향으로만 이동가능하다면 

dp[i][j] = dp[i-1][j] + dp[i][j-1] 입니다.

하지만 이문제에서는 이동할 수 없는 구간들이 있습니다. 

그렇기 때문에 이러한 부분은 표시해주어야 합니다.

저는 bool construction[201][201] 배열을 통해서 해결했습니다.

construction[b+d][a+c] = 1 값을 저장해주면서 진행했습니다.

이때 dp[i][j]는 

if (construction[2 * i - 1][2 * j] == 0)
   dp[i][j] += dp[i - 1][j];
if (construction[2 * i][2 * j - 1] == 0)
   dp[i][j] += dp[i][j - 1];

입니다.

아래는 정답코드입니다.

#include <iostream>
using namespace std;

int n = 0, m = 0, k = 0;
int a, b, c, d;
bool construction[201][201] = { 0, };
unsigned long long dp[101][101] = { 0, };
int y_ar[2] = { 0,-1 };
int x_ar[2] = { -1,0 };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	cin >> k;

	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c >> d;
		construction[b + d][a + c] = 1;
	}
	dp[0][0] = 1;

	for (int i = 1; i <= m; i++) {
		if (construction[2 * i - 1][0] == 1)
			break;
		dp[i][0] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (construction[0][2 * i - 1] == 1)
			break;
		dp[0][i] = 1;
	}


	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (construction[2 * i - 1][2 * j] == 0)
				dp[i][j] += dp[i - 1][j];
			if (construction[2 * i][2 * j - 1] == 0)
				dp[i][j] += dp[i][j - 1];


		}
	}

	cout << dp[m][n] << endl;
	return 0;
}

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

문제의 핵심 조건은 N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.

수의 범위가 작기때문에 긴 차원의 배열을 만들어도 된다는 것을 알게되었습니다.

모든 경우를 고려해주는 것으로 생각을 가지게 되었습니다.

 무려 7차원 배열입니다.

dp[dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current] = 5종류의 구슬이 arr[i] 개씩 남아있고, 이전 구슬이 prefer, 현재 선택한 구슬이 current일때의 경우의 수의 합입니다.

그렇다면 재귀식은 아래 처럼 구현할 수 있습니다.

long long solved(int prefer, int current,int cnt) {
	if (cnt == sum) {
		return 1;
	}
	
	long long &ret = dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 1; i <= n; i++) {
		if (prefer != i && current != i && arr[i]) {
			arr[i]--;
			ret += solved(current, i, cnt+1);
			arr[i]++;
		}

	}

	return ret;
}

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

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

int n = 0, result = 0,sum=0;
int arr[6] = { 0, };
long long dp[11][11][11][11][11][6][6] = { 0, };

long long solved(int prefer, int current,int cnt) {
	if (cnt == sum) {
		return 1;
	}
	
	long long &ret = dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 1; i <= n; i++) {
		if (prefer != i && current != i && arr[i]) {
			arr[i]--;
			ret += solved(current, i, cnt+1);
			arr[i]++;
		}

	}

	return ret;
}

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

	return 0;
}

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

먼가 구현과 dp 중간느낌의 문제였습니다.

장애물을 피하면서 아이템을 모두 들렀다가 최종지점인 n,m에 도착하는 경우에 수 입니다.

이때 n,m은 위, 오른쪽으로만 이동이 가능하기 때문에, 쉬운 문제였습니다. 

• 1. 모든 아이템 좌표 저장하기 (저장후 정렬을 통해서 이동 순서 정해주기)
• 2. 이동 순서대로 이동하면서 dp가 채워주기 

 dp[i][j]는 기본적으로 dp[i-1][j] + dp[i][j-1]입니다.

만약 이전에 장애물이었다면 dp[i-1][j] 이나 dp[i][j-1]하나만

더해주고, 둘다 장애물이었다면 그대로 0입니다. 

아래는 정답코드입니다.

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

typedef struct MyStruct
{
	int y;
	int x;
}game;

vector <game> item;
int arr[102][102] = { 0, };
int dp[102][102] = { 0, };
int n = 0, m = 0, a, b;

bool cmp(game a, game b) {
	if (a.x < b.x) return 1;
	else if (a.x == b.x) {
		if (a.y < b.y) return 1;
	}
	return 0;
}

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

	cin >> n >> m >> a >> b;
	int temp_y,temp_x;
	for (int i = 1; i <= a; i++) {
		cin >> temp_y >> temp_x;
		item.push_back({ temp_y,temp_x });
		arr[temp_y][temp_x] = 1;
	}
	item.push_back({ n,m });
	for (int i = 1; i <= b; i++) {
		cin >> temp_y >> temp_x;
		arr[temp_y][temp_x] = -1;
	}
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << arr[i][j] << ' ';
		cout << endl;
	}
	*/
	dp[1][0] = 1;
	sort(item.begin(), item.end(), cmp);

	int current_y = 1, current_x = 1;

	for (int cnt = 0; cnt < item.size(); cnt++) {
		int des_y = item[cnt].y;
		int des_x = item[cnt].x;

		for (int i = current_y; i <= des_y; i++) {
			for (int j = current_x; j <= des_x; j++) {
				if (arr[i][j] == -1)
					dp[i][j] = 0;
				else if (arr[i - 1][j] != -1 && arr[i][j - 1] != -1) {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
				else if (arr[i - 1][j] != -1) {
					dp[i][j] = dp[i - 1][j];
				}
				else if (arr[i][j - 1] != -1)
					dp[i][j] = dp[i][j - 1];
			}
		}

		current_y = des_y;
		current_x = des_x;
	}
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << arr[i][j] << ' ';
		cout << endl;
	}
	cout << endl;

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

	cout << dp[n][m] << endl;
	return 0;
}

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

골드 3의 난이도는 아니였습니다. 다만 아이디어를 생각하는데 조금 어려움을 겪었습니다.

경우는 총 3가지 입니다.

올라갔다 다시 내려가는 경우 -> {10, 20, 30, 25, 20}

오름차순 ->{10, 20, 30, 40}

내림차순 ->{50, 40, 25, 10}

오름차순과 내림차순의 dp는 O(n^2)으로 쉽게 구할수 있습니다.

각각을 dp[i]와 dp_reverse[i]라고 하겠습니다.

올라갔다 내려가는 경우는 

dp[i] + dp_reverse[i] - 1 입니다. 해당 i에서의 오름차순 값 + 내림차순 값 - 1입니다. -1을 하는 이유는 자기자신이 두번 더해졌기 때문입니다. 

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

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

int dp[1002];
int dp_reverse[1002];
int n = 0;
int arr[1001] = { 0, };
int result = 1;

void solve_forward() {

	for (int i = 2; i <= n; i++) {

		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i])
				if (dp[i] < dp[j] + 1)
					dp[i] = dp[j] + 1;

		}
	}
}
void solve_backward() {
	for (int i = n - 1; i >= 1; i--) {
		for (int j = i + 1; j <= n; j++) {
			if (arr[j] < arr[i])
				if (dp_reverse[i] < dp_reverse[j] + 1)
					dp_reverse[i] = dp_reverse[j] + 1;
		}

	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = 1;
		dp_reverse[i] = 1;
	}
	
	solve_forward();
	solve_backward();
	
	for (int i = 1; i <= n; i++) {

		if (dp[i] + dp_reverse[i] - 1 > result)
			result = dp[i] + dp_reverse[i] - 1;
		
		if (dp[i] > result)
			result = dp[i];
		else if (dp_reverse[i] > result)
			result = dp_reverse[i];
		
	}
	cout << result << endl;
	return 0;

}

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

내리막길 문제와 유사해서 크게 어렵지는 않았습니다.

예를 들어서, 단순히 오른쪽, 아래로만 이동하는게 아니라 위에 올라갔다가, 왼쪽으로 갔다가 올 수도 있기 때문에

모든경우를 탐색해주어야하는 이때, dp의 메모이제이션을 사용하는 식입니다.

dp의 UP-DOWN 방식으로 구현을 하자는 아이디어를 얻었습니다.

점화식은 아래처럼 구현했습니다. 이때 ny, nx는 인접한 4방향 좌표를 모두 탐색합니다.

if (ny >= 1 && ny <= n&&nx >= 1 && nx <= n)
			if (arr[y][x] < arr[ny][nx]) {
				ret = max(ret, solved(ny, nx) + 1);
		}

고민했던 부분은 모든 좌표에서 재귀함수를 호출하면 시간이 오래걸리지 않을까? 입니다.

근데 이때 dp는 초기화할 필요가 없기때문에 시간적으로 오래걸리지 않습니다.

dp[i][j]는 i,j 좌표에서 이동할 수 있는 최대값을 의미합니다.

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

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

int n = 0;
int arr[501][501] = { 0, };
int dp[501][501];
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
int result = 0;

int solved(int y, int x) {
	int &ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (ny >= 1 && ny <= n&&nx >= 1 && nx <= n)
			if (arr[y][x] < arr[ny][nx]) {
				ret = max(ret, solved(ny, nx) + 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++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
				result = max(result, solved(i, j));
			
		}

	cout << result + 1 << endl;
	return 0;
}

dp라고 인식되는  순간 체감난이도가 확 줄었습니다.

이해가 안되시면 천천히 디버깅해보세요!

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

dp라는걸 모르고 풀었음 더 어려웠을 문제였습니다. 
처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생겼습니다.

예를 들어서, 단순히 오른쪽, 아래로만 이동하는게 아니라 위에 올라갔다가, 왼쪽으로 갔다가 올 수도 있기 때문입니다.

 
그래서 모든 경우를 탐색해주어야 한다고 인식하게 되었고, dp의 UP-DOWN 방식으로 구현을 하자는 아이디어를 얻었습니다.

점화식은 아래처럼 구현했습니다. 이때 ny, nx는 인접한 4방향 좌표를 모두 탐색합니다.

if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}

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

#include <iostream>
#include <cstring>
using namespace std;
/*
	dp라고 모르고 풀었음 더 어려웠을 문제
	처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생김
	모든 경우를 탐색해주어야 한다고 인식하게 됨 -> UP-DOWN 방식으로 구현
*/
int m, n;
int arr[501][501] = { 0, };
int dp[501][501] = { 0, };

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

int solved(int y, int x) {
	if (y == 1 && x == 1)
		return 1;
	int &ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}
	}

	return ret;
}

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

	cin >> m >> n;

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

	memset(dp, -1, sizeof(dp));
	cout << solved(m,n) << endl;

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

dp라고 인식되는  순간 체감난이도가 확 줄었습니다.

이해가 안되시면 천천히 디버깅해보세요!

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

반례를 못찾아서 고생한 문제입니다.

양팔저울을 통해서 구슬의 무게를 잴 수있는지 확인하는 문제입니다. 모든 경우를 확인해주어야 합니다.

근데 이때 재귀를 사용하여 해결할 수 있고 dp를 활용하자는 생각을 가지는 것이 문제 접근의 핵심입니다.

첫 번째, dp구현하기

dp[i][j]는 i는 현재 무게, j는 탐색하는 추의 인덱스 입니다.

두 번째, 재귀 점화식 도출

모든 경우를 다 고려해야 합니다. 즉, 

ret = solved(abs(weight - sinker[i]), i + 1);
ret = max(ret, solved(weight, i + 1));
ret = max(ret, solved(weight + sinker[i], i + 1));

3가지를 고려해야 합니다.

이때 abs(weight - sinker[i]) 부분 때문에  고생했습니다.

저는 처음에 

if (sinker[i] <= weight) {
ret = solved(weight - sinker[i], i + 1);
}

이렇게 구현했습니다. 근데 이때 추보다 작은 무게가 먼저 들어올때 추를 사용하지 않고 넘어가다보니 오류가 났습니다.

해결하기위해서 2가지 방법이 있습니다.

1. 인덱스를 사용하기 

2. 그냥 절대값으로 해결하기

저는 2번을 선택했습니다. 절대값으로 고려하여도 저울의 어느쪽에 두는지의 차이이기 때문에 상관이 없습니다.

아래는 정답코드입니다.

코드를 천천히 따라가면서 이해해보세요

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a = 0, b = 0;
int sinker[31] = { 0, };
int arr[7] = { 0, };
int dp[100001][31];


int solved(int weight, int current) {
	if (weight == 0)
		return 1;
	if (current > a)
		return 0;

	int &ret = dp[weight][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = current; i <= a; i++) {

		ret = solved(abs(weight - sinker[i]), i + 1);
		ret = max(ret, solved(weight, i + 1));
		ret = max(ret, solved(weight + sinker[i], i + 1));
		return ret;
	}
}

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

	cin >> a;
	for (int i = 1; i <= a; i++)
		cin >> sinker[i];

	cin >> b;
	for (int i = 1; i <= b; i++) {
		int temp;
		cin >> temp;
		memset(dp, -1, sizeof(dp));

		
		if (solved(temp, 1))
			cout << 'Y';
		else
			cout << 'N';

		if (i != b)
			cout << ' ';
	}
	cout << endl;
	return 0;

}