[BOJ] 12969번 - ABC

백준 12969번 - ABC

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	1143	578	401	49.384%

문제

정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오.

• 문자열 S의 길이는 N이고, 'A', 'B', 'C'로 이루어져 있다.
• 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍이 K개가 있다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2)

 

출력

첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다.

 

---

예제 입력 1

3 3

예제 출력 1

ABC

예제 입력 2

3 0

예제 출력 2

CBA

예제 입력 3

5 10

예제 출력 3

-1

예제 입력 4

15 36

예제 출력 4

CABBACCBAABCBBB

 

출처

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

12969번: ABC

알고리즘 분류

• 다이나믹 프로그래밍

접근 방법

먼저, 이 문제를 Brute Force 방식으로 접근 할 경우 3^30 의 경우의 수가 생기고, 이를 모두 연산하는 것은 TLE이다.

이 중에서 Promising 하지 않은 경우, 해당 값으로 탐색을 계속 진행하는 것을 피하기 위해선 어떤 방식으로 접근해야할까?

 

K(0<= K < N) 위치에 올 수 있는 경우의 수는 3가지(A,B,C)이다. 그렇다면, K-1까지 구한 문자열에 A, B, C 를 삽입했을 때 

0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍은 몇 개가 추가될까? 해당 쌍을 P라고 표현하겠다.

 

K위치에 'A'가 추가되었을 때, 추가되는 P는 없다.

K위치에 'B'가 추가되었을 때, 추가되는 P는 이전까지 문자열에 존재하는 A의 개수이다.

K위치에 'C'가 추가되었을 때, 추가되는 P는 이전까지 문자열에 존재하는 A,B의 개수이다.



이러한 사항들을 모두 고려를 하였을 때, 이전의 문자열에 존재하는 A,B,C의 개수가 매우 중요한 것을 알 수 있다.

 

백트래킹을 진행해주되, Promising 한 것이 아닐 경우 가지치기를 해준다.

Promising 한 경우가 아닌 것은 "이전까지의 A,B의 개수와 쌍(P)의 개수가 동일할 경우로 탐색을 진행하였을 때, 정답이 아니였던 것"

이 되겠다. 즉, 다음과 같은 경우는 뒤에 A,B,C가 추가되는 모든 상황에서 동일하다고 볼 수 있다.

 

예를 들어 다음과 같은 상황은 동치라고 볼 수 있다.

ABBAC

BAABC

이 2개는 모두 이전까지의 A와 B의 개수가 같고 P의 개수 또한 동일하기 때문에, 뒤에 (A,B,C)중 어떠한 것이 추가되더라도 동일한 결과를 도출하는 것이 자명하다.

 

이러한 경우를 가지치기 하기 위해선, 현재 상태(state)를 메모이제이션 하는 것이 핵심이다.

{현재 문자열의 길이, 현재까지 A의 개수, 현재까지 B의 개수, (현재까지 C의 개수), 쌍의 개수(P)} 를 표현하는 테이블을 정의하자.

단, 현재 문자열의 길이 - (현재까지 A의 개수 + 현재까지 B의 개수) 를 통해 (현재까지 C의 개수)를 구할 수 있으므로 테이블의 크기를 생각하여  4차원 테이블로 표현할 수 있다.

 

DP[i][j][k][r] = 현재 길이가 i이고 이전까지의 A의 개수가 j 이전까지의 B의 개수가 k 이고 만들어 진 쌍의 개수가 r인 경우를 탐색해봤는가? 

 

로 테이블을 정의하자.

 

그렇게 할 경우, 백트래킹을 시도할 때 Promising하지 않은 경우를 모두 필터링하므로서 경우의 수를 대폭 줄일 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, K;
bool dp[31][31][31][450] = {false,};
char ans[31];
bool solve(int n, int a, int b, int p){
    if( n == N ){
        if( p == K ){
            cout << ans;
            exit(0);
        }
        else
            return false;
    }

    if( dp[n][a][b][p] ){
        // 이미 이전에 이러한 쌍을 시도했지만, 정답이 나오지 못한 경우이므로
        // 추가 탐색을 진행하지 않고 종료한다.
        return false;
    }
    dp[n][a][b][p] = true;

    ans[n] = 'A';
    solve(n+1, a+1, b, p);
    ans[n] = 'B';
    solve(n+1, a, b+1, p+a);
    ans[n] = 'C';
    solve(n+1, a, b, p+a+b);

    return false;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> K;
    solve(0, 0, 0, 0);

    cout << -1;
    return 0;
}