[BOJ] 백준 12969. ABC (Gold I)

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제.

문제는 아래와 같다.

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

12969번: ABC

N<=30 이라는 정말 애매한 범위여서 고민을 좀 했는데,

풀이를 적어보도록 하겠다.

---

의식의 흐름 및 해설

처음 생각난 것은 백트래킹이었으나, N이 30이기 때문에 백트래킹은 커녕 TSP도 어려워보였다.

 

그 다음은 수학적 성질을 생각해보았는데,

적절한 칸에 A를 넣고, 그 A의 왼쪽 구간은 다 순서쌍 개수를 1씩 빼버리는 방법을 진행해볼까 했는데,

결국 이 방법도 브루트포스였다. 따라서 빠르게 패스.

 

어딘가에서 최적화할 수 있을까 고민해보니,

현재까지 길이에서의 순서쌍의 개수를 메모이제이션할 수 있지 않을까? 생각하다가, A, B, C 개수를 어떻게 썼느냐에 따라 메모이제이션이 달라지겠다 싶어서,

현재까지 A, B, C를 각각 몇 개 썼을 때, 순서쌍의 개수를 메모이제이션해놓는 방법을 쓸 수 있을 듯했다. 

마침 30^5는 약 3천만에 가까운 수였기 때문에 시간복잡도로도 충분했다.

 

s[i]<s[j] 순서쌍의 개수는 결국 A가 i개, B가 j개, C가 k개 있을 때,

A를 사용하게 되면 A보다 작은 알파벳은 없으므로 그대로,

B를 사용하게 되면 이전에 사용한 A i개와 순서쌍을 맺을 수 있으므로 i개 추가,

C를 사용하게 되면 이전에 사용한 A i개 + B j개와 순서쌍을 맺을 수 있으므로 i+j개 추가가 된다.

이렇게 dp식으로 계속 추가하면서 K개일 때 true가 리턴되면 그 때의 결과를 출력해주면 된다.

 

dp식에서 결과값이 아닌, 결과로 가능한 값을 리턴하게 해주는 특이한 식이었다.

기억해두면 좋을 듯?

---

시행착오

처음에 아래처럼 메모이제이션 안하고 값을 리턴하다가 시간초과를 받았다.

true, false 리턴식이다보니 깜빡했던 듯...

int& ret = d[a][b][c][k];
if (~ret)return ret;
ans[a + b + c] = 0;
if (dp(a + 1, b, c, k))return 1;	// 메모이제이션 X
ans[a + b + c] = 1;
if (dp(a, b + 1, c, k - a))return 1;	// 메모이제이션 X
ans[a + b + c] = 2;
if (dp(a, b, c + 1, k - a - b))return 1;	// 메모이제이션 X
return 0;	// 메모이제이션 X

아래처럼 메모이제이션을 해주어야 한다.

int& ret = d[a][b][c][k];
if (~ret)return ret;
ans[a + b + c] = 0;
if (dp(a + 1, b, c, k))return ret=1;
ans[a + b + c] = 1;
if (dp(a, b + 1, c, k - a))return ret=1;
ans[a + b + c] = 2;
if (dp(a, b, c + 1, k - a - b))return ret=1;
return ret=0;

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 33;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, K, d[MAX][MAX][MAX][453], ans[MAX];
int dp(int a, int b, int c, int k) {
	if (a + b + c == N)return !k ? 1 : 0;
	if (k <= 0)return 0;
	int& ret = d[a][b][c][k];
	if (~ret)return ret;
	ans[a + b + c] = 0;
	if (dp(a + 1, b, c, k))return ret = 1;
	ans[a + b + c] = 1;
	if (dp(a, b + 1, c, k - a))return ret = 1;
	ans[a + b + c] = 2;
	if (dp(a, b, c + 1, k - a - b))return ret = 1;
	return ret = 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> K;
	memset(d, -1, sizeof(d));
	if (!K) {
		for (int i = 0; i < N; i++) {
			cout << 'A';
		}
		return 0;
	}
	if (!dp(0, 0, 0, K)) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		cout << (char)(ans[i] + 'A');
	}
}

---

재밌는 dp문제였다.

다른 분들 보니까 백트래킹이 가능하다는 의견이 있던데,

메모이제이션 안하면 시간초과 나는 듯해서 일단 난 dp 태그만 붙였다.

 

또, 다른 분들 보니까 이러한 형태의 점화식이 Well-Known이라는 분들도 꽤 있었다.

확실히 많이 풀어보면서 경험해봐야될 듯.

 

요즘 우테코 활동을 하느라 백준은 감 유지 정도만 하고 있는데,

한번 다음에 BOJ 대회도 참여하든지 해봐야겠다.