백준 12969번 ABC - C++(cpp) 풀이

---

 

1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)이다.
2. dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부
3. 따라서 'A'로 시작하는 경우, 'B'로 시작하는 경우, 'C'로 시작하는 경우를 모두 고려하면, dp(a, b, c, k) = dp(a-1, b, c, k-b-c) 또는 dp(a, b-1, c, k-c) 또는 dp(a, b, c-1, k)

 

1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)이다.

 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍을 간단히 '오름차순 쌍'이라고 하자. 이러한 오름차순 쌍을 K개 가진 문자열 S가 있고, S앞에 어떠한 문자 X를 붙여 새로운 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)와 같다. 기존 문자열 S에 존재하는 문자 Y가 새로 추가된 문자 X와 오름차순 쌍을 이루기 위해서는 Y가 X보다 사전 순으로 나중이기만 하면 된다. X가 항상 Y보다 앞에 나오기 때문이다.

 

2. dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부

 1번 사실을 이용해서 DP로 해결할 수 있다. dp(a, b, c, k)를 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재여부라고 하자. 이때 구해야 하는 dp값은 약 N^5개이고, N이 최대 30이므로 시간 내에 해결이 가능하다.

 

3. 따라서 'A'로 시작하는 경우, 'B'로 시작하는 경우, 'C'로 시작하는 경우를 모두 고려하면, dp(a, b, c, k) = dp(a-1, b, c, k-b-c) 또는 dp(a, b-1, c, k-c) 또는 dp(a, b, c-1, k)

 dp(a, b, c, k)는 문자열의 시작 문자에 따라 경우를 나누어 구할 수 있다. 문자열이 'A'로 시작하는 경우에는 'A'의 개수가 한 개 줄고, 맨 앞 'A'에 의해 오름차순 쌍이 k-b-c개 생길 것이므로 결괏값은 dp(a-1, b, c, k-b-c)가 될 것이다. 'B'와 'C'의 경우도 마찬가지로 같은 방법으로 구해주면 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

int N, K;
int cache[31][31][31][900];

// dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부
int dp(int a, int b, int c, int k) {
    if (k < 0) return 0;
    if (a + b + c == 1) return k == 0;
    
    int& ret = cache[a][b][c][k];
    if (ret != -1) return ret;
    
    int sa = a > 0 ? dp(a-1, b, c, k-b-c) : 0;
    int sb = b > 0 ? dp(a, b-1, c, k-c) : 0;
    int sc = c > 0 ? dp(a, b, c-1, k) : 0;
    
    ret = sa + sb + sc;
    if (ret > 1) ret = 1;
    
    return ret;
}

string backtrack(int a, int b, int c, int k) {
    if (a + b + c == 1) {
        if (a == 1) return "A";
        if (b == 1) return "B";
        if (c == 1) return "C";
    }
    
    if (a > 0 && dp(a-1, b, c, k-b-c)) return "A" + backtrack(a-1, b, c, k-b-c);
    if (b > 0 && dp(a, b-1, c, k-c)) return "B" + backtrack(a, b-1, c, k-c);
    if (c > 0 && dp(a, b, c-1, k)) return "C" + backtrack(a, b, c-1, k);
    
    return "-1";
}

string solution() {
    memset(cache, -1, sizeof(cache));
    
    for (int a=0; a<=N; a++) {
        for (int b=0; b<=N-a; b++) {
            int c = N - a - b;
            if (dp(a, b, c, K) != 0) return backtrack(a, b, c, K);
        }
    }
    
    return "-1";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    cout << solution();
    
    return 0;
}