[백준] 12969 ABC

문제

정수 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을 출력한다.

==

솔루선

• 문자열에 A를 추가하면 s[i]<s[j] 를 만족하는 쌍은 이전까지의 sum과 같음 
• 문자열에 B를 추가하면 s[i]<s[j] 를 만족하는 쌍은 이전까지의 sum에 A의 갯수를 더하는 것이 됨
• 문자열에 C를 추가하면 s[i]<s[j] 를 만족하는 쌍은 이전까지의 sum에 A의 갯수 + B의 갯수를 더하는 것이 됨
• 시간 초과를 방지하기 위해 visited[a][b][c][k]를 통해 방문 했는지 체크 (N의 최댓값은 30, K의 최댓값은 450이 되므로 abc는 31로 k는 451로 생성)
• 큐에는 이전까지의 a,b,c의 갯수를 같이 넣어서 체크 해줌

from collections import deque


def sol(n, k):
    if not k:
        return "A"*n
    dx = ["A", "B", "C"]
    q = deque()
    q.append((0, 0, 0, 0, 0, []))
    visited = [[[[False]*(451)for _ in range(31)] for _ in range(31)]
               for _ in range(31)]
    visited[0][0][0][0] = True
    while (q):
        sum_k, a, b, c, cur, arr = q.popleft()

        if (sum_k > k):
            continue
        if (cur == n):
            if (sum_k == k):
                return "".join(arr)
            else:
                continue
        for i in range(3):
            nx = dx[i]
            if (i == 0 and visited[a+1][b][c][sum_k] == False):
                visited[a+1][b][c][sum_k] = True
                q.append((sum_k, a+1, b, c, cur+1, arr+[nx]))

            if (i == 1 and visited[a][b+1][c][sum_k+a] == False):
                visited[a][b+1][c][sum_k+a] = True
                q.append((sum_k+a, a, b+1, c, cur+1, arr+[nx]))

            if (i == 2 and visited[a][b][c+1][sum_k+a+b] == False):
                visited[a][b][c+1][sum_k+a+b] = True
                q.append((sum_k+a+b, a, b, c+1, cur+1, arr+[nx]))
    return -1


n, k = map(int, input().rsplit())
print(sol(n, k))