PS) 백준 1958, 2225, 17069, 17070, 1655번 (LCS3, 합분해, 파이프 옮기기1, 2, 가운데를 말해요)

 

백준 1958번 LCS3

 

문자열 3개의 가장 긴 부분수열을 구하는 프로그램

문자열만 하나 많아졌을 뿐 구현하는 방법은 2개일때와 같음!

dp[i][j][k] => 문자열 1의 i번째 문자, 문자열 2의 j번째 문자, 문자열 3의 k번째 문자까지 중에서 lcs의 길이

배열을 3차원으로 설정하고 구현해주면 됨. 모든 문자가 같은 경우 이전 문자열의 최장수열길이에서 1을 더해준것을 기록하고, 문자가 다른 경우 이전 탐색한 수열의 최댓값을 기록한다.

 

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string>
using namespace std;
int dp[105][105][105];

//문자열 3개의 LCS를 구하는 프로그램
int main() {
	string str1, str2, str3;
	cin >> str1 >> str2 >> str3;
	int len1, len2, len3; 
	len1 = str1.length(); len2 = str2.length(); len3 = str3.length();
	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			for (int k = 1; k <= len3; k++) {
				if (str1[i - 1] == str2[j - 1] && str3[k - 1] == str1[i - 1])
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
				else 
					dp[i][j][k] = fmax(fmax(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
			}
		}
	}
	printf("%d", dp[len1][len2][len3]);
}

 

 

 

 

2225번 합분해

 

이전에 풀었던 동전 문제와 비슷하다. 처음에 배열을 3차원으로 구현해야하는 문제인 줄 알았다.

[정수 k를 더해서 총 j개의 정수를 더했을 때, i를 만들 수 있는 경우의 수] 이렇게 생각했었다. 그러나 점화식을 생성하던 중에 계속 2차원만 생각해주면 되는 문제인듯해서 2차원으로 구현해주었다. 이 문제는 배열은 2차원이지만 for문이 3중으로 중첩되어야 한다!!

 

dp[i][j]를 정수 j개를 더해서 i를 만들 수 있는 경우의 수로 설정한다.

특별히 정수 j개를 더해서 0을 만드는 경우의 수는 1이다. => 0+0+0+0 같은 형태도 세주어야 하므로

정수 j개를 더해서 i를 만드는 경우의 수는, 정수 j-1개를 더해서 0, 1, 2, 3 ~ i를 만드는 경우의 수와 같다. 

(j개를 더하는 차례에 i, i-1, i-2, i-3 ~ 0 을 더하여 i를 만들 것이므로)

 

#include<stdio.h>
#define MOD 1000000000;
int dp[205][205]; //dp[i][j] = 정수 j개를 더해 i를 만들 수 있는 경우의 수

int main() {
	int n, k; scanf("%d%d", &n, &k);
	for (int j = 0; j <= k; j++) dp[0][j] = 1; //정수 j개를 더해 0을 만드는 경우의 수는 한개임 0+0+0..
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			for (int l = 0; l <= i; l++) {
				//정수 j개를 더해 i를 만드는 경우의 수는 정수 j-1개를 더해 n-i를 더하는 수와 같다 
				//->정수 j개를 더하는 차례에 n-i를 더해줄 것이므로
				dp[i][j] = (dp[i][j] + dp[i - l][j - 1]) % MOD;
			} 
		}
	}
	int sum = dp[n][k];
	printf("%d", sum);
}

 

 

 

 

17070번 17069번 파이프 옮기기1, 2

 

문제가 길었지만 긴 문제의 특징은 문제에서 하라는 대로 다 하면 쉽게 풀린다(아직까지는..).

dp[i][j][1,2,3] = i번, j번에 가로(1)로, 세로(2)로, 대각선(3)으로 위치하고 있는 경우의 수

처음부터 탐색하면서 갈 수 있는 곳이 벽이 아니라면 갈 수 있는 경우를 설정해주면 된다.

중간에 한번 막힌 이유는 가로나 세로와는 다르게 대각선에서는 대각선을 둘러싼 세개의 벽이 모두 뜷려있을 경우에 대각선으로 이동할 수 있다는 점이다. 

 

#include<stdio.h>
int arr[35][35];//집의 상태
long long dp[35][35][3];

int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	dp[1][2][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j+1] == 0) { //이동할 수 있으면 이동
				dp[i][j+1][1] += dp[i][j][1] + dp[i][j][3];
			}
			if (arr[i + 1][j] == 0) {
				dp[i + 1][j][2] += dp[i][j][2] + dp[i][j][3];
			}
			if (arr[i + 1][j + 1] == 0 && arr[i+1][j]==0 && arr[i][j+1]==0) {
				dp[i + 1][j + 1][3] += dp[i][j][1] + dp[i][j][2] + dp[i][j][3];
			}
		}
	}
	printf("%lld", dp[n][n][1] + dp[n][n][2] + dp[n][n][3]);
}

가로, 대각선으로 이동 시 (백준 문제 이미지 캡쳐)

 

 

파이프 옮기기1 문제도 궁금해서 봤는데 파이프 옮기기2와 거의 동일하다. 자료형만 바꿔주면 파이프 옮기기2 문제임 ! 코드는 2와 1이 거의 같아서.. 안올림!

 

 

 

1665 가운데를 말해요

 

 

2주 전 풀었는데,, 틀렸습니다 떠서 묵혀둔 문제.. 다시 새로 푸는 마음으로 고쳤더니 맞았다.

이 문제는 사실 구현해내는 것보다 어떻게 풀지 아이디어를 떠올리는 것이 7할이라.. 그 당시 푸는 방법을 다른 블로그에서 참고했던 것으로 기억한다.  TL = 0.1초, n = 10만개의 데이터를 각각 받으면서, 이때까지 받은 수들의 중앙값을 출력하는 문제이다. 중앙값을 알기 위해서 새로운 값이 들어올 때마다 일일히 정렬해주게 되면 무조건 시간초과가 발생한다(가장 효율적으로 정렬하는 알고리즘을 써도 k번째 데이터에서 => klgk) 그렇기 때문에 중앙값을 기준으로 작은 값을 저장하는 큐, 큰 값을 저장하는 큐를 두개 구현하고, 값이 들어올 때마다 알맞은 큐에 넣어준다. 항상 중앙값을 maxheap에 위치시키도록 비교해서 옮겨준다 => 이 부분에서 구현이 헷갈림.. 정렬시간은 k번째 데이터에서 lg(k/2)의 시간이 걸리므로 매우 효율적이다. 

맞았긴 하지만 일주일 내로 한번 더 깔끔히 풀어볼 예정이다!!

 

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;
void maxtomin(int a) {
	minheap.push(maxheap.top());
	maxheap.pop();
	maxheap.push(a);
}
void mintomax(int a) {
	maxheap.push(minheap.top());
	minheap.pop();
	minheap.push(a);
}
int main() {
	int t; scanf("%d", &t);
	int a;

	for (int i = 1; i <= t; i++) {
		scanf("%d", &a);
		if (maxheap.size() == 0) {
			maxheap.push(a);
		}
		else if (minheap.size() == 0) {
			if (maxheap.top() > a) maxtomin(a);
			else minheap.push(a);
		}
		else if (minheap.size() > maxheap.size()) {
			if (minheap.top() > a)	maxheap.push(a);
			else mintomax(a);
		}
		else if (maxheap.size() > minheap.size()) {
			if (maxheap.top() >= a) maxtomin(a);
			else  minheap.push(a);
		}
		else { //둘의 사이즈가 같다
			if (minheap.top() > a) maxheap.push(a);
			else mintomax(a);
		}
		printf("%d\n", maxheap.top());
	}
}