Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-12969-ABC

import sys
input = sys.stdin.readline

N,K = map(int, input().split())

dp = [[[[0 for _ in range(K+1)] for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0][0] = 1
# add A
result = ""
def add_char(n_a, n_b, n_c, k):
    global result
    if n_a+n_b+n_c==N and k==K:
        return 1

    if n_a+1 < N+1 and dp[n_a+1][n_b][n_c][k] == 0:
        dp[n_a+1][n_b][n_c][k] = 1
        if add_char(n_a+1,n_b,n_c,k) == 1:
            result += 'A'
            return 1
    if n_b+1 < N+1 and k+n_a < K+1 and dp[n_a][n_b+1][n_c][k+n_a] == 0:
        dp[n_a][n_b+1][n_c][k+n_a] = 1
        if add_char(n_a,n_b+1,n_c,k+n_a) == 1:
            result += 'B'
            return 1
    if n_c+1 < N+1 and k+n_a+n_b < K+1 and dp[n_a][n_b][n_c+1][k+n_a+n_b] == 0:
        dp[n_a][n_b][n_c+1][k+n_a+n_b] = 1
        if add_char(n_a,n_b,n_c+1,k+n_a+n_b) == 1:
            result += 'C'
            return 1
    
    return 0

exist = add_char(0,0,0,0)
if exist == 0:
    print(-1)
else:
    print(result[::-1])
Comments