[2021 acm-icpc] 7/7 연습 문제

1. SCPC 2018 1차 예선 2 - 회문인 수의 합

풀이

 

처음에 알고리즘 분류를 DP로 알고 있어서 DP로 생각하다가 우주 갔다가 돌아온 문제이다.

 

이 문제는 브루트포스로 해결이 가능했다. 

브루트포스에서 가장 중요한 점인 시간 복잡도만 체크해보자. (아이디어는 떠올리기 어렵지 않다)

 

먼저 n제한은 10000이고 시간 제한은 1초이다.

즉 O(n제곱)은 성립하지 않는다.

 

그렇다면 이곳저곳에서 컷팅을 시도해보자.

 

먼저 우리가 체크해야 할 것은 총 3가지 이다.

 

1. 자기 자신이 바로 회문인 경우

2. 2개의 회문의 합으로 이루어진 경우

3. 3개의 회문의 합으로 이루어진 경우

 

자기 자신이 회문인 경우는 1~10000까지 각각 체크해주면 되므로 O(1만)이다.

 

2번째 경우 역시 마찬가지로 1~10000까지 i와 n-i가 각각 회문인지 확인하면 되므로 O(1만)이다.

라고 넘어가면 아쉽지요

잘 생각해보면 어차피 i와 n-i를 비교하는 것이기 때문에 절반인 5000까지만 비교하면 된다.

(1 + 4999 = 4999 + 1이니까)

따라서 시간복잡도는 O(5000)이 된다.

 

3번째 경우가 사실상 핵심이다.

일반적인 브루트포스라면 O(n제곱), 즉 O(1억)이 되지만 무수한 컷팅이 가능하다. (거의 반쪽으로)

3가지 수 중 첫 번째 수는 2번째 경우와 마찬가지로 5000까지로 고정이 가능하다. 

그럼 남은 두 개의 수 역시 1~5000 범위 내의 수일 것이다.

이 때 단순하게 이중 for문을 5000, 5000으로 잡으면 안된다.

이유는 나머지 두 수가 합쳐서 (n - 첫 번째 수)가 되어야 한다.

이때 반드시 n - 첫 번째 수가 5000안에 든다고 할 수 있을까? 없다. (ex. n = 7777, i = 1이면 ...)

따라서 정확하게 n - 첫 번째 수로 범위를 정해줘야 한다.

최악의 경우 n = 10000,  i = 1일 수 있으므로 시간 복잡도는 O(5000*10000) = O(5천만)이다.

 

따라서 각 테스트 케이스마다 모든 값을 계산하는데에는 대략 O(5천만), 0.5초 정도가 소요된다.

더 컷팅하거나 시간을 줄일 방법이 있는지는.. 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int dp[10007];

// 회문 검사 -> string으로 변환 후 검사
int pallindrom(int x) {
	string str = to_string(x);
	int s = 0, e = str.size() - 1;
	for (int i = 0; i < (str.size() / 2); i++) {
		if (str[s] != str[e]) return 0;
		s++; e--;
	}
	return 1;
}

int main() {
	// dp[] table 채우기
	for (int i = 1; i < 10001; i++) dp[i] = pallindrom(i);
	// 입력
	int T, Answer, test_case, n;
	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		// 입력받기
		cin >> n;
		// 출력
		cout << "Case #" << test_case + 1 << "\n";
		bool stop = false;
		// 숫자 하나로 회문 가능한 경우
		if (dp[n] == 1) {
			cout << "1 " << n << "\n";
			continue;
		}
		// 숫자 두 개로 회문 가능한 경우
		for (int i = 1; i < n; i++) {
			if (dp[i] == 1 && dp[n - i] == 1) {
				cout << 2 << " " << n - i << " " << i << "\n";
				stop = true;
				break;
			}
		}
		if (stop) continue;
		// 숫자 세개로 회문 가능한 경우
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < n - i; j++) {
				if (dp[i] == 1 && dp[j] == 1 && dp[n - i - j] == 1) {
					vector<int>v = { i,j,n - i - j };
					sort(v.begin(), v.end(), greater<int>());
					cout << 3 << " " << v[0] << " " << v[1] << " " << v[2] << "\n";
					stop = true;
					break;
				}
			}
			if (stop) break;
		}
		if (stop) continue;
		cout << 0 << "\n";
	}

	return 0;

}

 

2. SCPC 2019 2차 예선 2 - 유사도

 

문제

 

n개의 숫자들로 이루어진 두 수열 A, B의 유사도는 1 ~ n까지 ai, bi 의 숫자가 일치하는 개수를 의미한다.

우리는 수열 B의 어떤 구간 [i, j] 를 뒤집어 유사도를 최적화시킬 수 있는데, 이때 가장 높은 유사도를 출력하면 된다.

 

 

풀이

 

문제에서 n 제한이 5,000 이므로 완전 탐색으로는 해결할 수 없다.

모든 구간을 선택하는 데에 O(n^2), 그 구간을 뒤집어 유사도를 측정하면 도합 O(n^3) 이기 때문이다.

 

하지만 어떤 구간 [i, j]의 유사도를 측정하는데, 이전에 구했던 유사도를 써먹을 수 있다.

이유는 [i, j] 구간을 뒤집는건 사실 [i + 1, j - 1] 구간을 뒤집고 + (i, j) 위치만 서로 바꾸어주면 되기 때문이다.

[i + 1, j - 1] 은 순차적으로 계산했을 때, [i, j] 구간을 구하기 전에 구하게되므로 시간복잡도 O(n^2) 로 해결 가능하다.

 

따라서 점화식은 다음과 같다.

 

dp[i][j] = dp[i + 1][j - 1] + (i, j 를 바꾸었을 때 손익 계산)

 

손익 계산은 a[i], a[j], b[i], b[j] 를 서로 비교해보면 금방 구할 수 있다.

 

다만, 위 점화식은 구간이 최소 3개는 포함하고 있어야 가능하므로, 구간 1~2개 짜리는 미리 구해두고 계산하자.

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int dp[5001][5001];

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{

		memset(dp, 0, sizeof(dp));
		int n; cin >> n;
		vector<int>a(n), b(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < n; i++) cin >> b[i];

		//1. 가만히 있을 경우, 유사도
		int sim = 0;
		for (int i = 0; i < n; i++) if (a[i] == b[i]) sim++;
		for (int i = 0; i < n; i++) dp[i][i] = sim;

		int ans = sim;
		for (int i = 0; i < n - 1; i++) {
			int ret = 0;
			if (a[i] == b[i]) ret--;
			if (a[i + 1] == b[i + 1]) ret--;
			if (a[i] == b[i + 1]) ret++;
			if (a[i + 1] == b[i]) ret++;
			dp[i][i + 1] = dp[i][i] + ret;
			ans = max(ans, dp[i][i + 1]);
		}


		for (int k = 2; k < n; k++) {
			for (int i = 0; i < n; i++) {
				int j = i + k;
				if (j >= n) break;
				int ret = 0;
				if (a[i] == b[i]) ret--;
				if (a[j] == b[j]) ret--;
				if (a[i] == b[j]) ret++;
				if (a[j] == b[i]) ret++;
				dp[i][j] = dp[i + 1][j - 1] + ret;
				ans = max(ans, dp[i][j]);
			}
		}
		
		cout << "Case #" << test_case+1 << "\n";
		cout << ans << "\n";
	}

	return 0;//Your program should return 0 on normal termination.
}

 

 

3. BOJ 1102 발전소(dp, 비트마스킹)

문제

https://www.acmicpc.net/problem/1102

1102번: 발전소

작동해야할 발전소 수를 입력 받아 최소 비용을 들여서 P개의 발전소를 돌리는 비용을 출력하시오

풀이

골드1 DP문제부터는 본격적으로 비트마스킹을 이용한 문제가 나옵니다.

일단 발전소의 출력은 -1 또는 0 이상의 최소 비용입니다. 하나의 발전소를 이용하여 다른 모든 발전소를 고칠 수 있는 것이 가능하기에 -1을 출력하는 케이스는 모든 발전소가 작동하지 않을 때인 케이스만 존재합니다.

코드는 top-down하여 풀었는데, 여기서는 작동하는 모든 발전소에서 왔다갔다하며 최소 비용을 구해야하기 때문에 dp[N][1<<N]이 아닌 dp[1<<N]으로도 구현할 수 있게 됩니다.

여기 부분은 2중 for문을 이용하여 현재 작동중인 발전소 i에서 꺼져있는 발전기 j를 돌리게 만들 수 있는 최소비용을 구하면서 값을 업데이트 하였습니다.

bit함수는 몇 개의 발전소가 작동되고 있는지 확인하는 함수인데, go함수에 작동하고 있는 발전기의 수인 total 변수를 추가하여 bit함수를 만들지 않아도 됩니다.

 

소스 코드(.cpp)

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

const int N = 16, MAX = 1e9;

int n, e, s = 0;
int cost[N][N], dp[1 << N];
string state;

int bit(int val) {
	int ans = 0;
	while (val != 0) {
		ans += (val & 1);
		val = val >> 1;
	}
	return ans;
}

int go(int visit) {
	if (bit(visit) >= e) return 0;
	int& ret = dp[visit];
	if (ret != -1) return ret;

	ret = MAX;
	for (int i = 0; i < n; i++) {
		if ((visit & (1 << i))) {
			for (int j = 0; j < n; j++) {
				if (!(visit & (1 << j))) {
					int next = visit | (1 << j);
					ret = min(ret, go(next) + cost[i][j]);
				}
			}
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof(dp));

	cin >> n;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> cost[i][j];
	
	cin >> state;
	for(int i = 0; i < n; i++)
		if (state[i] == 'Y') s |= (1 << i);
	
	cin >> e;
	if (bit(s) == 0) {
		if (e == 0)cout << 0 << endl;
		else cout << -1 << endl;
	}
	else {
		int ans = go(s);
		cout << ans << endl;
	}
}