14238. 출근 기록

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C)이다.

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

A는 매일 매일 춘그할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다.

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.

출력

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 업는 경우에는 -1을 출력한다.

코드

ss = input()

n = len(ss)
cnt1 = 0 # a의 개수
cnt2 = 0 # b의 개수
cnt3 = 0 # c의 개수

for s in ss :
  if s == 'A' : cnt1 += 1
  elif s == 'B' : cnt2 += 1
  else : cnt3 += 1

# [a][b][c][pre1][pre2]
dp = [[[[[-1 for _ in range(3)] for _ in range(3)] for _ in range(51)] for _ in range(51)] for _ in range(51)]

answer = ""
def solve (a,b,c,pre1,pre2) :
  global answer
  if a+b+c == n :
    return True

  result = dp[a][b][c][pre1][pre2]
  if result != -1 :
    return result

  if a+1 <= cnt1 :
    if solve(a+1,b,c,0,pre1) == 1 :
      answer = "A" + answer
      dp[a][b][c][pre1][pre2] = 1
      return 1
  
  if b+1 <= cnt2 and pre1 != 1 :
    if solve(a,b+1,c,1,pre1) == 1 :
      answer = "B" + answer
      dp[a][b][c][pre1][pre2] = 1
      return 1
  
  if c+1 <= cnt3 and pre1 != 2 and pre2 != 2 :
    if solve(a,b,c+1,2,pre1) == 1 :
      answer = "C" + answer
      dp[a][b][c][pre1][pre2] = 1
      return 1
  
  dp[a][b][c][pre1][pre2] = 0
  return 0

solve(0,0,0,0,0)
print(-1) if answer == "" else print(answer)