[BOJ] 14238 출근 기록

14238 출근 기록 문제 링크
문제 풀이 코드 링크

문제 요약

A, B, C 세 명의 직원이 있고, 하루에 한명씩 출근한다.

• A는 매일매일 출근할 수 있다.
• B는 출근한 다음날 쉬어야한다.
• C는 출근한 다음날과 다다음날을 쉬어야한다.

A, B, C로 이루어진 문자열이 주어지고, 해당 문자열의 순열에 대해 가능한 출근 기록을 (종류 상관없이) 출력한다.

아이디어

앞서 풀었던 비즈 공예와 같은 형식의 문제이다. 다차원 DP 배열.

문자열에서 A, B, C가 각각 몇 개인지 세면, 해당 수가 이 조합에서 사용할 수 있는/사용해야하는 개수이다. 해당 개수와 이전 2단계에 누가 출근했는지에 따라 DP 배열을 갱신한다.

DP 배열은 [A의 남은 수][B의 남은 수][C의 남은 수][2단계 전 출근기록][1단계 전 출근 기록]의 형태로 설계할 수 있다.

마찬가지로 TOP-DOWN의 형태로 풀이할 수 있다. 매 단계마다 출근하는 사람을 선택하고, 해당 사람의 남은 수를 1개 줄이고 다음 함수를 재귀적으로 호출한다. 매 단계는 남은 출근 기록 수와 2단계 전 출근 기록에 따라, 남은 출근 기록을 완성할 수 있는 경우의 수를 반환하며, 반환 값은 해당 DP 배열에 저장된다.

구현

import sys

input = sys.stdin.readline

S = input()

count = [0 for i in range(3)]

count[0] = S.count("A")
count[1] = S.count("B")
count[2] = S.count("C")

A, B, C = 0, 1, 2

intToChar = {0: 'A', 1: 'B', 2: 'C', -1:''}


dp = [[[[[True for p2 in range(4)] for p in range(4)] for c in range(count[C] + 1)] for b in range(count[B] + 1)] for a in range(count[A] + 1)]

def DFS(cur, pre) :
  if dp[count[A]][count[B]][count[C]][pre][cur] == False :
    return False

  if count[A] == 0 and count[B] == 0 and count[C] == 0 :
    print(intToChar[cur], end="")
    return True

  # A
  if count[A] > 0 :
    count[A] -= 1
    success = DFS(A, cur)
    count[A] += 1

    if success :
      print(intToChar[cur], end="")
      return True

  # B
  if cur != B and count[B] > 0:
    count[B] -= 1
    success = DFS(B, cur)
    count[B] += 1

    if success :
      print(intToChar[cur], end="")
      return True

  # C
  if pre != C and cur != C and count[C] > 0:
    count[C] -= 1
    success = DFS(C, cur)
    count[C] += 1
    
    if success :
      print(intToChar[cur], end="")
      return True
  
  dp[count[A]][count[B]][count[C]][pre][cur] = False
  return False

result = DFS(-1, -1)
if not result :
  print(-1)