이것 저것 &

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

dp문제입니다. 

두가지의 다리가 있고 

1. 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.
2. 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.
3. 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1과 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

라는 규칙을 만족해야 합니다.

저는 각각 천사다리dp 와 악마다리dp를 만들어 문제를 해결했습니다.

RGS일때 

와 같은 표를 만들 수 있습니다. 각 행의 값 dp[i][j] 는 dp[k][j-1]의 합이 됩니다. (k는 0~i까지 반복)

dp문제의 핵심은 점화식을 유도하는 것입니다.

이해가 되시지 않는다면 규칙과 표를 다시 한번 비교해보세요.

 정답코드입니다.

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

string a;
string angel;
string devil;

int dp[100][21] = { 0 };
int dp2[100][21] = { 0 };
int result = 0;
int main() {
	cin >> a;
	cin >> angel;
	cin >> devil;

	for (int i = 0; i < angel.size(); i++) {
		if (angel[i] == a[0]) dp[i][0] = 1;
		if (devil[i] == a[0]) dp2[i][0] = 1;
	}

	for (int i = 0; i < angel.size(); i++) {

		for (int j = 1; j < a.size(); j++) {
			if (angel[i] == a[j]) {
				int cnt = 0;
				for (int k = 0; k < i; k++)
					if (dp2[k][j - 1] != 0) cnt += dp2[k][j - 1];
				dp[i][j] = cnt;
			}
			if (devil[i] == a[j]) {
				int cnt = 0;
				for (int k = 0; k < i; k++)
					if (dp[k][j - 1] != 0) cnt += dp[k][j - 1];
				dp2[i][j] = cnt;
			}

		}

	}

	for (int i = 0; i < angel.size(); i++) {
		result += dp[i][a.size() - 1];
		result += dp2[i][a.size() - 1];
	}
	cout << result << endl;
}

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

팰린드롬은 앞으로 보나 뒤로 보나 대칭인 값입니다. 

해당 팰린드롬 만들기를 구현하기 위해서는 dp 관점으로 접근해야합니다. 

저는 직관적인 점화식을 유추하지 못했습니다.

분명 재귀를 쓰지않고 구현하는 방법이 있을텐데, 못찾고 인터넷의 힘을 빌렸습니다.

우선 정답코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n = 0, result = 0;
int arr[5001] = { 0 };
int dp[5001][5001] = { 0 };

int solved(int started, int ended) {
	if (started == ended || started > ended) return 0;

	int& ret = dp[started][ended];
	if (ret != -1) return ret; //방문햇엇고, 이미 결과가 있으면 그걸 사용한다는 것 
	ret = 0;

	if (arr[started] == arr[ended])
		ret += solved(started + 1, ended - 1);

	else {
		ret += min(solved(started, ended - 1) + 1, solved(started + 1, ended) + 1);
	}

	return ret;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	memset(dp, -1, sizeof(dp));

	result = solved(0, n - 1);

	cout << result << endl;

	return 0;
}

up-down 방식으로 구현하였습니다 

5

1 2 3 4 2 와 같은 예시에서

1 2 3 4 2 에서  양끝 1 과 2를 비교합니다. 두 값이  같지않을 때 두가지 방법이 존재합니다.

• 1을 가르키는 화살표를 오른쪽 방향으로 옮기고 2뒤에 1를 추가한다.  ->  1 2 3 4 2 (1)
• 2를 가르키는 화살표를 왼쪽 방향으로 옮기고  1앞에 2를 추가한다.    ->  (2) 1 2 3 4 2

만약 두값이 같다면 화살표를 둘다 안쪽으로 옮기고 값을 유추합니다. -> 1 2 3 4 2 (1)   -> 1 2 3 4 2 (1)  

 1 2 3 4 2 (1) 이와같은 상황에서는 두가지 방법을 적용해보고 그중 작은 값을 반환합니다. (1을 반환하게 됩니다.)

3 4 3 or 4 3 4  구조가 되면 내부적으로 1을 반환합니다. 

결과값은 1 2 3 4 (3) 2 (1) 으로 2가 됩니다. 

재귀함수를 통해 구현하며 ret 값이 -1이 되었다면 이미 한번 탐색한 곳이기 때문에 바로 해당값을 반환합니다.(메모이 제이션)

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

공통 부분 문자열을 찾는 문제입니다. n의 범위가 4000까지입니다.

일반적인 구현방법을 생각해볼때 O(n^3)이 됩니다. 이때 최악의 경우 64,000,000,000 번 반복되기에 당연히 시간초과입니다.

n^2 번의 계산법을 찾아야합니다. 

저는 표를 만들어 보며 규칙을 찾았습니다. 

보이시나요? 이전 배열값에서 1을 더한 값이 자신의 최대연속배열값입니다.

점화식은 dp[i][j] = dp[i - 1][j - 1] + 1 입니다. 

정답코드입니다.

#include <iostream>
#include <string>
using namespace std;
string arr;
string arr2;
int dp[4001][4001] = { 0 };
int result = 0;
int main() {
	cin >> arr;
	cin >> arr2;

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[0] == arr2[j]) {
			dp[0][j] = 1;
			if (result < dp[0][j]) result = dp[0][j];
		}
	}

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[j] == arr2[0]) {
			dp[j][0] = 1;
			if (result < dp[j][0]) result = dp[j][0];
		}	
	}


	for (int i = 1; i < arr.size(); i++) {
		for (int j = 1; j < arr2.size(); j++) {
			if (arr[i] == arr2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (result < dp[i][j]) result = dp[i][j];
			}
		}
	}
	cout << result << endl;

}

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

dp문제입니다.

수의 범위가 0~20까지 밖에 되지않고 값이 2^63-1 이라고 명시해주었기 때문에 dp로 풀 수 있는 문제였습니다. 

• 초기값으로 배열에 처음 값을 넣어줍니다.
• 이전배열에서 이전배열값들에서 현재값을 더하거나 빼서 얻을 수 있는 값들을 현재배열에 저장합니다.
• 이 과정을 반복한후 마지막값의 인덱스의 현재배열값을 출력합니다. 

정답코드입니다.

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

int n = 0, val = 0;
int arr[100] = { 0 };
long long before[21] = { 0 };
long long current[21] = { 0 };

int main() {
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		cin >> arr[i];
	}
	cin >> val;

	before[arr[0]] = 1; //초기값 지정
	for (int i = 1; i < n - 1; i++) {
		memset(current, 0, sizeof(current));
		for (int j = 0; j <= 20; j++) {
			if (before[j] != 0){
				if ((j + arr[i]) <= 20)
					current[(j + arr[i])] += before[j];
				if((j - arr[i]) >= 0)
					current[(j - arr[i])] += before[j];
			}
		}
		for (int j = 0; j <= 20; j++)
			before[j] = current[j];

	}

	cout << current[val] << '\n';
}

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

쉬운 dp 문제입니다.

윗단의 값들을 통해서 점화식을 유추할 수 있습니다.

//1.
dp[i][0] = arr[i][0] + max(dp[i - 1][0], dp[i - 1][1]);
//2.
dp[i][1] = arr[i][1] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
//3.
dp[i][2] = arr[i][2] + max(dp[i - 1][1], dp[i - 1][2]);

왼쪽은 왼쪽이랑 가운데로 부터, 가운데는 3군데 모두, 오른쪽은 오른쪽이랑 가운데로 부터 올 수있기 때문입니다.

다만 시간초과를 조심하셔야 합니다. 

4 MB이기 때문에 메모리 제한에 주의하셔야 합니다. 

arr같은경우 값을 전부 받고 dp는 dp[2][3] 으로 이전값과 현재 dp 값을 저장하는 용도로 사용하였습니다. 

(arr도 더 줄일 수 있는 문제였습니다.) 

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int arr[100000][3] = { 0 };
int maxed[2][3] = { 0 };
int mined[2][3] = { 0 };
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

	maxed[0][0] = mined[0][0] = arr[0][0];
	maxed[0][1] = mined[0][1] = arr[0][1];
	maxed[0][2] = mined[0][2] = arr[0][2];

	for (int i = 1; i < n; i++) {
		maxed[1][0] = arr[i][0] + max(maxed[0][0], maxed[0][1]);
		maxed[1][1] = arr[i][1] + max(max(maxed[0][0], maxed[0][1]), maxed[0][2]);
		maxed[1][2] = arr[i][2] + max(maxed[0][1], maxed[0][2]);

		maxed[0][0] = maxed[1][0];
		maxed[0][1] = maxed[1][1];
		maxed[0][2] = maxed[1][2];

		mined[1][0] = arr[i][0] + min(mined[0][0], mined[0][1]);
		mined[1][1] = arr[i][1] + min(min(mined[0][0], mined[0][1]), mined[0][2]);
		mined[1][2] = arr[i][2] + min(mined[0][1], mined[0][2]);

		mined[0][0] = mined[1][0];
		mined[0][1] = mined[1][1];
		mined[0][2] = mined[1][2];

	}
	cout << max(max(maxed[0][0], maxed[0][1]), maxed[0][2]) << ' ' << min(min(mined[0][0], mined[0][1]), mined[0][2]) << endl;

}

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

dp문제입니다.

위와 같을때 값을 2*2 =4입니다. 각 점마다 자신의 넓이는 이전 점들의 값과 연관이 있습니다.

점화식은 arr[i][j] 가 1인점에 한해서 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1], dp[i][j] ) + 1 입니다. 

이전 값들의 크기에 따라서 값이 변하게 되는 구조입니다.

저는 초기값 설정을 어설프게 해서 한번 틀렸었습니다.

1행과 1열 모두 초기값 설정을 해야합니다.

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

int dp[1001][1001] = { 0 };
int result = 0, n = 0, m = 0;
string arr[1001];

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

	for (int i = 0; i < n; i++) {
		dp[i][0] = arr[i][0] - '0';
		result = max(result, dp[i][0]);
	}
	for (int i = 0; i < m; i++) {
		dp[0][i] = arr[0][i] - '0';
		result = max(result, dp[0][i]);
	}

	for (int i = 1; i < n; i++) 
		for (int j = 1; j < m; j++) {
			if (arr[i][j] == '1') {
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]);
				dp[i][j] = min(dp[i][j - 1], dp[i][j]);
				dp[i][j]++;
			}
			if (result < dp[i][j])
				result = dp[i][j];
		}
	cout << result*result << '\n';
}

구현자체에 어려움은 없으실 것입니다. 

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

전형적인 DP 문제였습니다.

1~9로 시작하는 값에 대한 테이블입니다.

즉, 1로 시작하는 네자리수는 5개 입니다. ( 1010, 1012, 1212, 1210, 1232, 1234)

이때    101~ 는  dp[2][1] 이구 12~ 는 dp[3][2] 입니다.

그외에 2~8로 시작하는 네자리수는 dp[i][j] = dp[i-1][j-1]+ dp[i-1][j+1]임을 확인할 수 있습니다. 

9로 시작할때는 98~이니 dp[i][j] = dp[i-1][j-1]

 즉 점화식은

arr[i][j] = arr[i - 1][j + 1] + arr[i - 2][j] (i=1일떄)

arr[i][j] = arr[i - 1][j + 1] + arr[i - 1][j - 1] (2~8)

arr[i][j] = arr[i - 1][j - 1] (i=9)

#include <iostream>
using namespace std;
int arr[101][10] = { 0 };
long long result = 0;
int n = 0;
int main() {
	cin >> n;	

	for (int i = 1; i <= 9; i++) // 초기값 설정
		arr[1][i] = 1;
	for (int j = 1; j <= 8; j++)
		arr[2][j] = 2;
	arr[2][9] = 1;

	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= 9; j++) {
			if (j == 1)
				arr[i][j] = (arr[i - 1][j + 1] + arr[i - 2][j]) % 1000000000;
			else if(j==9)
				arr[i][j] = (arr[i - 1][j - 1]) % 1000000000;
			else 
				arr[i][j] = (arr[i - 1][j + 1] + arr[i - 1][j - 1]) % 1000000000;
			
		}
	}

	for (int i = 1; i <= 9; i++) {
		result += arr[n][i];
	}
	result %= 1000000000;

	cout << result << endl;
}

arr 연산식마다 %1000000000 를 해주어야 오버플로우를 피할 수 있습니다. int 형의 범위를 넘어갈 수 있기 때문입니다.

반면 result는 long long 형으로 정의했기 때문에 1~9까지의 값을 다 더하고 나눠도 지장이 없습니다.

위 테이블을 보고 직접 점화식을 유추해보세요! 화이팅!

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

이항계수를 출력하는 문제입니다. 

당연히 팩토리얼을 계산해서 푸는 방식이 아닙니다. 팩토리얼 방식으로 하면, 곱하기 과정에서 아주 큰 값이 나오게 되기 때문에 오버플로우가 발생합니다. (int, longlong 둘다) 

중간중간에 나머지를 해주는 방식도 생각해보았지만, 어떠한 규칙을 적용해야할지 모르겠네요..

dp문제입니다.

dp란? 순차적인 결과물에서 특정 점화식에 의해서 값이 도출되는 형태를 의미합니다.

아래 그림은 파스칼 삼각형입니다. 이항계수를 구할 때 사용됩니다. 

감이 오시나요?

dp알고리즘의 핵심은 점화식 구하기 입니다. 

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] << 라는 점화식을 구하실 수 있을거에요

아래는 정답코드입니다. 아마 구현하는데 어려움은 없을실 겁니다. 

#include <iostream>
using namespace std;

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

int main() {
	cin >> n >> k;

	for (int i = 1; i <= n + 1; i++) {
		dp[i][1] = 1, dp[i][i] = 1;
		for (int j = 2; j <= i - 1; j++) {
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}
	cout << dp[n + 1][k + 1] << '\n';
}