[BAEKJOON] 2565, 5582, 22252

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold5, 2565 전깃줄] - 최장증가부분수열(LIS)

LIS의 가장 큰 특징은, 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성할 수 있다
그래서 lower_bound를 활용하여, LIS의 원소를 업데이트 하면 최종 길이를 구할 수 있다

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N;
struct Data {
	int idx, conn;
};
Data elec_line[101];

bool elecCompare(Data a, Data b) {
	return a.idx < b.idx;
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int fs, se;
		scanf("%d %d", &fs, &se);
		elec_line[i] = { fs, se };
	}
	sort(elec_line, elec_line + N, elecCompare);

	int low[101];
	int len = 0;
	low[0] = elec_line[0].conn;
	for (int i = 1; i < N; i++) {
		if (elec_line[i].conn > low[len]) {
			low[++len] = elec_line[i].conn;
		}
		else {
			int idx = lower_bound(low, low + len, elec_line[i].conn) - low;
			low[idx] = elec_line[i].conn;
		}
	}
	printf("%d", N - len - 1);
}

 

[gold5, 5582 공통 부분 문자열] - 최장 공통 부분 문자열(Longest Common Substring)
단어가 일치하는 연속 부분 문자열을 찾는 과정은 다음과 같다
1) 문자열 A, B에 대해 행렬 DP을 초기화한다.
2) A[i] == B[j]일 때, DP[i][j] = 1이 되며, 문자열이 연속되는 경우 DP[i - 1][j - 1]에 값이 있다
2-1) DP[i - 1][j - 1]의 값에 따라 결정된다. 즉, DP[i][j] = DP[i - 1][j - 1] + 1;
3) DP[i][j]가 갱신될 때, 그 중 최대값이 LCS가 된다

#include <iostream>
#include <string>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int dp[4001][4001];
int main() {
	string str1, str2;
	cin >> str1;
	cin >> str2;

	size_t len1 = str1.length(), len2 = str2.length();

	int answer = 0;
	for (size_t i = 1; i <= len1; i++) {
		for (size_t j = 1; j <= len2; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}  
			answer = answer > dp[i][j] ? answer : dp[i][j];
		}
	}
	printf("%d", answer);
}

 

[gold5, 22252 정보 상인 호석] - 우선순위 큐 + 맵

맵에 우선순위 큐를 할당할 수 있다
 
호식이가 정보를 살 때
1) 맵의 우선순위 큐가 비어있는지 확인
2) 맵의 우선순위 큐의 크기가 b보다 작은지 확인
2-1) 만약 b보다 작다면, 우선순위 큐의 내용만큼만 정보 가치합산
2-2) b보다 크다면, b만큼만 정보 가치합산
 
2-1, 2-2 과정에서 우선순의 큐의 정보 가치를 합산한 맵을 활용하여 시간초과를 해결할 수 있다
정보들의 가치 총합의 범위가 10^6*10^6으로 10^10을 가뿐히 넘어가, long long 자료형을 사용해야 하는 것에 유의한다

#include <iostream>
#include <queue>
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define ll long long
map <string, priority_queue<int>> m;
map <string, ll> s;
int main() {
	int Q, query;
	ll answer = 0;
	scanf("%d", &Q);
	for (int q = 0; q < Q; q++) {
		string name;
		cin >> query >> name;
		if (query - 1) {
			int b;
			scanf("%d", &b);
			if (m[name].empty()) continue;
			if (m[name].size() <= b) {
				answer += s[name];
				s[name] = 0;
				m[name] = priority_queue<int>();
			}
			else {
				ll cnt = 0;
				for (int i = 0; i < b; i++) {
					cnt += m[name].top(); m[name].pop();
				}
				answer += cnt;
				s[name] -= cnt;
			}
		}
		else {
			int k, C;
			scanf("%d", &k);
			for (int i = 0; i < k; i++) {
				scanf("%d", &C);
				m[name].push(C);
				s[name] += C;
			}
		}
	}
	printf("%lld", answer);
}