굳건하게

문제 : https://www.acmicpc.net/problem/1958

[알고리즘풀이]

기존의 LCS 문제에서 문자열이 하나 더 추가로 들어온 문제이다.

( 기존 풀이 링크 LCS1 : https://travelbeeee.tistory.com/150 )

( 기존 풀이 링크 LCS2 : https://travelbeeee.tistory.com/151 )

입력된 3개의 문자열을 n1 , n2, n3 라고 하자. 또 dp배열을 다음과 같이 정의하자.

dp[i][j][k]

: n1 의 i번 째 문자열, n2의 j번 째 문자열, n3의 k번 째 문자까지 중에서  최장 공통 부분 수열의 길이.

그러면 다음과 같은 점화식이 성립한다.

1) n1의 i번 째 문자와 n2의 j번 째 문자, n3의 k번 째 문자가 같다면.

   dp[i][j][k] = dp[i-1][j-1][k-1] + 1

   i번 째 문자와 j번 째 문자, k번 째 문자가 같으므로,

   그 전인 (i -1)번 째 문자와 (j - 1)번 째 문자, (k - 1)번 째 문자까지의 길이의 최대 길이에 1을 더해주면 된다.

2) 셋 다 같지 않다면.

   dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

   지금까지 탐색한 가장 큰 값을 저장해주면 된다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int dp[101][101][101];

int main(void) {
	string n1, n2, n3;
	cin >> n1 >> n2 >> n3;
	int n = n1.length(), m = n2.length(), l = n3.length();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			for (int k = 1; k <= l; k++) {
				if (n1[i - 1] == n2[j - 1] && n2[j - 1] == n3[k - 1])
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
				else {
					dp[i][j][k] = max(dp[i - 1][j][k], max(dp[i][j - 1][k], dp[i][j][k - 1]));
				}
			}
		}
	cout << dp[n][m][l];

}

문제 : https://www.acmicpc.net/problem/9252

[알고리즘풀이]

기본적인 틀은 LCS 문제와 같다.

( LCS 기본 문제 : https://travelbeeee.tistory.com/150 )

입력되는 2개의 문자열을 n1, n2 라고 하자. 그리고 다음과 같이 dp배열을 선언해 string과 int를 동시에 담아보자.

pair<string, int> dp[i][j]

dp[i][j].first : n1 의 i번째 문자, n2의 j번째 문자까지 중에서 최장 공통 부분 수열의 문자열.

dp[i][j].second : n1 의 i번째 문자, n2의 j번째 문자까지 중에서 최장 공통 부분 수열의 길이.

1) n1의 i번 째 문자와 n2의 j번 째 문자가 같다면.

dp[i][j].first = dp[i - 1][j - 1].first + n1[i - 1];  // 기존의 가장 큰 문자열에다가 현재 문자를 합쳐준다.
dp[i][j].second = dp[i - 1][j - 1].second + 1; // 기존의 가장 길이에다가 1을 더해준다.

i번 째 문자와 j번 째 문자가 같으므로 그 전인 (i -1)번 째 문자와 (j - 1)번 째 문자까지의 최대 길이에 1을 더해주면 된다.

또, (i - 1)번 째 문자와 (j - 1)번 째 문자까지의 최대 부분 수열에 현재 문자를 더해주면 된다.

2) n1의 i번 째 문자와 n2의 j번 째 문자가 다르다면.

  2-1) dp[i - 1][j].second < dp[i][j - 1].second)
           dp[i][j] = dp[i][j - 1];
  2-2)
           dp[i][j] = dp[i - 1][j];

i번 째 문자와 j번 쨰 문자가 다르면 지금 탐색하는 i, j 지점에서 길이가 길어지지 않으므로,

그전까지 탐색해온 값 중 가장 큰 값과 그에 해당하는 문자열을 저장해준다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

pair<string, int> dp[1001][1001];

int main(void) {
	string n1, n2;
	cin >> n1 >> n2;
	int n = n1.length(), m = n2.length();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (n1[i - 1] == n2[j - 1]) {
				dp[i][j].first = dp[i - 1][j - 1].first + n1[i - 1];
				dp[i][j].second = dp[i - 1][j - 1].second + 1;
			}
			else {
				if (dp[i - 1][j].second < dp[i][j - 1].second)
					dp[i][j] = dp[i][j - 1];
				else
					dp[i][j] = dp[i - 1][j];
			}
		}
	cout << dp[n][m].second << '\n';
	cout << dp[n][m].first << '\n';
}

문제 : https://www.acmicpc.net/problem/9251

[알고리즘풀이]

입력되는 2개의 문자열을 n1, n2 라고 하자.

dp[i][j] : n1 의 i번째 문자, n2의 j번째 문자까지 중에서 최장 공통 부분 수열의 길이 라고하자.

그러면 다음과 같은 식이 성립한다.

1) n1의 i번 째 문자와 n2의 j번 째 문자가 같다면.

dp[i][j] = dp[i-1][j-1] + 1

i번 째 문자와 j번 째 문자가 같으므로 그 전인 (i -1)번 째 문자와 (j - 1)번 째 문자까지의 최대 길이에 1을 더해주면 된다.

2) n1의 i번 째 문자와 n2의 j번 째 문자가 다르다면.

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

i번 째 문자와 j번 쨰 문자가 다르면 지금 탐색하는 i, j 지점에서 길이가 길어지지 않으므로,

그전까지 탐색해온 값 중 가장 큰 값을 저장해준다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int dp[1001][1001];

int main(void) {
	string n1, n2;
	cin >> n1 >> n2;
	int n = n1.length(), m = n2.length();
	
	for(int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (n1[i - 1] == n2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	cout << dp[n][m];
}

문제 : https://www.acmicpc.net/problem/5054

[알고리즘풀이]

가게 N개를 방문하는 모든 경우의 수를 생각해 봐야 될 것 같으나, 사실은 가게의 집들을 Sort 한 후, 맨 앞에서부터 차례대로 가게를 방문하고 돌아오면 된다. 거리를 최소화해야 되기 때문에, 가게를 뒤죽박죽 방문할 필요가 없다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int t, n, N[20];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> N[i];
		}
		sort(N, N + n);

		int ans = 0, cur = N[0], s = N[0];
		for (int i = 0; i < n; i++) {
			ans += abs(N[i] - cur);
			cur = N[i];
		}
		ans += abs(s - cur);
		cout << ans << '\n';
	}
}