[파이썬] 백준 12969 : ABC (골드1)

[파이썬] 백준 12969 : ABC (골드1)

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

---

문제

문제
정수 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을

---

풀이

방향성 생각

• 전체 경우의 수 : 3^30
• 경우의 수를 구하는 문제가 아니라, 조건을 만족하는 문자열 중 하나를 출력
• 재귀든 DP 역추적이든 문자열을 구해야한다.
• A가 a개, B가 b개, C가 c개일 때 K개의 쌍을 만드는 경우가 하나의 상태이다.
• 한 상태로 여러 번 도달하는 경우, 탐색이 여러 번 일어날 수 있다.
• 메모제이션을 통해 시간초과 줄이기.
  

전체코드

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

answer = None
dp = set()

def dfs(string,a,b,c,k):

    global answer

    if answer is not None:
        return

    if (a,b,c,k) in dp:
        return 

    if k == K: # 한 문자열만 찾으면, 남은 문자열은 A로 채워서 출력
        answer = string + (N-(a+b+c))*'A'
        return

    if k > K or a+b+c >= N:
        return

    dfs(string+'A',a+1,b,c,k)
    dfs(string+'B',a,b+1,c,k+a)
    dfs(string+'C',a,b,c+1,k+a+b)
    dp.add((a,b,c,k))

dfs('',0,0,0,0)
print(answer if answer else -1)

• 리스트가 더 빠르긴 한데, 배열 사이즈 지정이 필요 없는 set으로 설정
• 조건을 만족하는 문자열의 개수가 아니라 조건을 만족하는 문자열 중 하나를 출력하는 문제라서, 가장 먼저 찾은 문자열에 A를 붙여서 출력한다.

코멘트

• 사실 ACB,BAC처럼 2개가 나오는 간단한 반례가 있는데도 생각을 못해서 메모제이션이 필요 없는 문제로 생각해서 없이 제출했다.