[ baekjoon ] 14238. 출근 기록

---

문제 링크(골드3)

---

## 14238. 출근 기록
import sys

s = input()

obj = [s.count(word) for word in ('A', 'B', 'C')] # A, B, C 개수 카운트
# dp[a 개수][b 개수][c 개수][전전날][전날]
dp = [[[[[False for _ in range(3)] for _ in range(3)] for _ in range(len(s))] for _ in range(len(s))] for _ in range(len(s))]

answer = [''] * len(s)

def dfs(a, b, c, prev):
  if [a, b, c] == obj:
    print(''.join(answer))
    sys.exit()

  if dp[a][b][c][prev[0]][prev[1]]:
    return False

  dp[a][b][c][prev[0]][prev[1]] = True
  
  if a + 1 <= obj[0]:
    answer[a + b + c] = 'A'
    if dfs(a + 1, b, c, [prev[1], 0]):
      return True

  if b + 1 <= obj[1]:
    answer[a + b + c] = 'B'
    if prev[1] != 1:
      if dfs(a, b + 1, c, [prev[1], 1]):
        return True

  if c + 1 <= obj[2]:
    answer[a + b + c] = 'C'
    if prev[0] != 2 and prev[1] != 2:
      if dfs(a, b, c + 1, [prev[1], 2]):
        return True

  return False

dfs(0, 0, 0, [0, 0])
print(-1)

5차원 배열을 선언하는 DP 문제이다.
B는 출근한 다음날은 반드시 쉬어야 하고,
C는 다음, 다음다음날을 반드시 쉬어야 한다.

그렇기 때문에 전날, 전전날 누가 일했는지 알아야 B와 C가 해당 날에 출근할 수 있는지 알 수 있다.

또한 A, B, C가 일할 수 있는 날이 정해져있으므로, 해당 배열에 각 사람이 출근한 날 수를 저장해놓아야 한다.

-> dp[A가 일한 횟수][B가 일한 횟수][C가 일한 횟수][전날 일한 사람][전전날 일한 사람]

내 코드에서는 A를 0, B를 1, C를 2로 두어 전날, 전전날 일한 사람을 확인했다.

  if dp[a][b][c][prev[0]][prev[1]]:
    return False
  dp[a][b][c][prev[0]][prev[1]] = True

위의 코드를 통해 시간초과를 없앨 수 있다. dp를 이용하는 이유이기도 하다.
이미 확인된 경우는 다시 확인하지 않는다.

또한
S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력하는 문제이므로
dfs 알고리즘을 이용해서 올바른 출근 기록인 경우 한번만 출력하게 한다.

해당 조건

  if [a, b, c] == obj:
    print(''.join(answer))
    sys.exit()

요건 복습 필수 문제인 듯하다.

• 파일합치기 문제도..