이것 저것 &

문제풀이: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/2023

에라토스 체 알고리즘을 사용하면 n=8일때 시간초과가 일어납니다.

오히려 체알고리즘을 사용하지 않고 문제 조건 처럼  왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수인지

순서대로 찾아주는 것이 효율적입니다.

이를 재귀함수를 통해서 구현했습니다.

• 1. 첫수를 항상 2,3,5,7로 시작한다.
• 2. 그 이후 숫자는 반복문을 통해서 소수인지 확인하며 진행한다. 
• 3. 재귀함수가 n번 탐색했다면 해당 수는 소수이므로 바로 출력한다.

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int n = 0;

bool checked(int num) {

	for (int i = 2; i*i <= num; i++) {
		if (num%i == 0)
			return false;
	}
	return true;
}

void dfs(int num, int len) {
	if (len == n) {
		cout << num << "\n";
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (checked(num * 10 + i))
			dfs(num * 10 + i, len + 1);
	}

	return;
}

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

	
	cin >> n;
	dfs(2, 1);
	dfs(3, 1);
	dfs(5, 1);
	dfs(7, 1);
	return 0;
}

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

dfs 문제였습니다.

이때 완전탐색 횟수를 줄이는게 핵심인 문제였습니다.

우선 첫번째 코드를 먼저 보시죠.

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

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	cost[current] += w;
	for (int i = 0; i < vec[current].size(); i++) {
		dfs(vec[current][i]);
	}
}

int main() {

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		dfs(h);
	}

	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	return 0;
}

일반적으로 생각할 수 있는 방법입니다. 

근데 이렇게 제출하면 당연히 시간 초과가 납니다. 

좀더 효율적으로 탐색할 수 없을까 고민을 하던중에 

dfs를 한번만 돌아도 되는 아이디어를 생각했습니다.

아래처럼 dfs(1)을 호출하고 줄줄이 이전 cost값을 더해주는 형태로 구현했습니다. 

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

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	for (int i = 0; i < vec[current].size(); i++) {
		cost[vec[current][i]] += cost[current];
		dfs(vec[current][i]);
	}
}

int main() {

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		cost[h] += w;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	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라고 인식되는  순간 체감난이도가 확 줄었습니다.

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