이것 저것 &

문제링크: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

문제링크: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/2573

dfs 유형으로 분류되지만... 사실 단순 구현문제였습니다.

빙산이 몇개인지 확인하고, 빙산을 녹이고, 하는 과정을 구현하여 결과를 도출하면 됩니다.

알고리즘입니다.

• 1. 빙산이 몇조각인지 확인하기
• 2. 두조각 이상인지 확인하기
• 3. 얼음 녹이기 
• 4. 얼음이 다녹은지 확인

빙하가 몇조각인지 확인할 때에는 dfs 나 bfs중 편한것을 사용하시면 됩니다. 

#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0, result = 0;
int arr[300][300] = { 0 };
int temp[300][300] = { 0 };
int x_ar[4] = { 0,0,-1,1 };
int y_ar[4] = { 1,-1,0,0 };


void dfs(int yy,int xx,int cnt) {
	temp[yy][xx] = cnt; //temp에 표시 

	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < n&&x >= 0 && x < m)
			if (arr[y][x] && temp[y][x] == 0) 
				dfs(y, x, cnt);
			
	}
}
void melt_ice() {
	int melt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) continue;
			melt = 0;
			for (int k = 0; k < 4; k++) {
				int y = i + y_ar[k];
				int x = j + x_ar[k];
				if (arr[y][x] == 0 && y >= 0 && y < n && x >= 0 && x < m)
					melt++;
			}

			if (arr[i][j] < melt) continue;
			else temp[i][j] = arr[i][j] - melt;
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			arr[i][j] = temp[i][j];
}


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

	while (1) {
		//1. 빙산이 몇조각인지 확인하기
		memset(temp, 0, sizeof(temp));
		int cnt = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (arr[i][j] && temp[i][j] == 0) {
					cnt++;
					dfs(i, j, cnt);
				}
		//2. 두조각 이상인지 확인하기 
		if (cnt >= 2) {
			cout << result << endl;
			return 0;
		}
		//3. 얼음 녹이기 
		memset(temp, 0, sizeof(temp));
		melt_ice();
		//4. 얼음이 다녹은지 확인
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (arr[i][j]) jud = true;

		if (jud == false) {
			cout << 0 << endl;
			return 0;
		}

		//카운트 증가
		result++;
	}
}

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

전형적인 dfs 문제입니다. 수의 범위도 20까지 이기때문에 무조건 dfs 구현이구나 생각했습니다.

생각보다 쉽게 문제를 풀어 의아했습니다. 별다른 가지치기를 하지 않고 ac를 받았기 때문입니다. 

#include <iostream>
#include <string>
using namespace std;
int result = 0;
bool al[26] = { 0 };
int x_ar[4] = { 0,0,1,-1 };
int y_ar[4] = { 1,-1,0,0 };
int r = 0, c = 0;
string arr[20];
void dfs(int yy,int xx,int cnt) {
	if (cnt > result) { 
		result = cnt; 
	}

	for (int i = 0; i < 4; i++) {
		int y = y_ar[i] + yy;
		int x = x_ar[i] + xx;
		if (y >= 0 && y < r && x >= 0 && x < c) {
			if (al[arr[y][x] - 65] == 0) {
				al[arr[y][x] - 65] = 1;
				dfs(y, x, cnt + 1);
				al[arr[y][x] - 65] = 0;
			}
		}
	}
	return;

}

int main(){
	cin >> r >> c;
	for (int i = 0; i < r; i++)
		cin >> arr[i];
	
	
	al[arr[0][0] - 65] = 1;
	dfs(0, 0, 1);
	al[arr[0][0] - 65] = 0;
			
	
	cout << result << endl;
}

왜 백트래킹에 들어가는지 아직도 잘 모르겠습니다...

대문자 A가 아스킷 코드값으로 65이기 때문에 아래와 같이 마킹을 해주었습니다.

화이팅!!

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

구현문제입니다. 문제를 꼼꼼하게 읽는 습관을 길러야 할 것같습니다.

문제 조건중  어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 라는 조건에 주목해야합니다.

6 5

1 6

2 4 5

2 1 2

2 2 3

2 3 4

2 5 6

와 같은 테스트 케이스에서 답은 0 입니다. 

과장된 이야기를 먼저 들은 사람이 나중에 진짜 이야기를 들어도 거짓말쟁이인게 들통납니다. 

즉 순서가 상관이 없는 문제입니다. 

알고리즘 입니다. 

1. 만약 진실을 알고 있는 사람이 있다면 해당 파티에서 거짓말을 못합니다.

2. 진실을 알고있는 사람과 함께 파티에 참여한 사람들이 있다면, 해당 사람들이 진실을 알고있다고 표시합니다.

3.  2번 조건이 부합하면 다시 처음 파티부터 확인합니다. 

	#include <iostream>
	using namespace std;
	int n = 0, m = 0, result = 0;
	int num = 0, temp = 0;
	bool knowlege[51] = { 0 };
	bool val[50] = { 0 };
	int arr[50][51] = { 0 };
	int arr_index[50] = { 0 };
	int main() {
		cin >> n >> m; //사람의 수와 파티의 수
	
		cin >> num;
		for (int i = 0; i < num; i++) {
			cin >> temp;
			knowlege[temp] = 1;
		}

		for (int i = 0; i < m; i++) {
			cin >> num;
			arr_index[i] = num;
			for (int j = 0; j < num; j++)
				cin >> arr[i][j];
		}
	
		for (int i = 0; i < m; i++) {

			for (int j = 0; j < arr_index[i]; j++) {
				int v = arr[i][j];

				if (knowlege[v] == 1) {
					val[i] = 1; // 이파티에서 거짓말을 못해 
					bool jud2 = true;
					for (int k = 0; k < arr_index[i]; k++)
						if (knowlege[arr[i][k]] == 0 && j != k)
							jud2 = false, knowlege[arr[i][k]] = 1;

					if (jud2 == false) {
						i = -1;
						break;
					}

				}
			}

		}
	
		for (int i = 0; i < m; i++)
			if (val[i] == 0) result++; 


	
		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/2140

전형적인 구현문제입니다. 

모서리의 숫자들이 주어질 때 해당 지뢰의 최대갯수를 찾는 문제였습니다.

생각해보면 최대개수이기때문에 지뢰가 있을 수 없는 장소들만 찾아주면 됩니다.

저는 #위치를 탐색하면서  주변(8방향)에 0이 포함되어있으면 해당 #은 지뢰가 없다고 표시해주는 방법으로 해결하였습니다. 

그리고 0이 없다면 해당 위치는 지뢰가 있는것이고 주변(8방향)값들은 값을 1씩 낮춰줌으로써 구현하였습니다.

#include <iostream>
#include <string>
using namespace std;
int n = 0, result = 0;
string arr[101];
int y_ar[8] = {-1,-1,0,1,1,1,0,-1};
int x_ar[8] = {0,1,1,1,0,-1,-1,-1};


// 규칙을 보다보면 8방향에 0이 있는 경우에만 폭탄이 없고 나머지는 폭탄이 있다고 가정
int main() {
	cin >> n;

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

	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++) {
			bool jud = true;
			for (int u = 0; u < 8; u++) {
				int y = i + y_ar[u];
				int x = j + x_ar[u];
				
				if (arr[y][x] == '0') {
					arr[i][j] = ' ';
					jud = false;
				}
			}
			if (jud == true) {
				for (int u = 0; u < 8; u++) {
					int y = i + y_ar[u];
					int x = j + x_ar[u];

					if ('0' < arr[y][x] &&  arr[y][x] <= '3') {
						arr[y][x] -= 1;
					}
				}
			}

		}
			
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++)
			if (arr[i][j] == '#') result++;
	
	cout << result << endl;

	return 0;
}