문제

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

방황

from itertools import combinations
n,k=map(int,input().split())
alpha=[]
for i in range(n):
    alpha.append('A')
    alpha.append('B')

l=list(combinations(alpha,n))
for a in l:
    count=0
    for i in range(n):
        for j in range(i+1,n):
            if a[i]=='A' and a[j]=='B':
                count+=1
            if count > k:
                break
        if count == k:
            answer=''.join(a)
            print(answer)
            exit(0)
print(-1)

처음에는 'A'와 'B'의 조합으로 경우의수를 만들어서 확인하면서 답을 찾고자하였다.
하지만 메모리 초과가나 버려서 다른 방법을 찾았다.

코드

n,k=map(int,input().split())

alpha=['B']*n
def check(alpha):
    count=0
    for i in range(n-1):
        if alpha[i]=='A':
            for j in range(i+1,n):
                if alpha[j]=='B':
                    count+=1
    return count

for i in range(n):
    alpha[i]='A'
    if check(alpha)==k:
        answer=''.join(alpha)
        print(answer)
        exit(0)
    if check(alpha)>k:
        alpha[i]='B'

print(-1)

처음에 'B'*n의 문자열을 만들고 'A'를 하나씩 넣어가면서 조건에 해당하는지 파악하는 방식이다.
조건의 개수가 k보다 클 경우만 정답이 아니므로 'B'로 복구하고 작을경우는 다음조건에서 정답이될 수 있으므로 넘어간다.
그리디의 정석같은 문제같았다.