[BOJ] 12996. Acka

---

문제 링크

---

s, a, b, c = map(int, input().split())

dp = [[[[-1 for _ in range(51)] for _ in range(51)] for _ in range(51)] for _ in range(51)]

def solve(n, a, b, c):
  if n == 0:
      if a == 0 and b == 0 and c == 0:
          return 1
      else:
          return 0

  if a < 0 or b < 0 or c < 0:
      return 0
      
  if dp[n][a][b][c] != -1:
      return dp[n][a][b][c]

  dp[n][a][b][c] = 0

  for i in range(2):
      for j in range(2):
          for k in range(2):
              if i + j + k == 0:
                  continue
              dp[n][a][b][c] += solve(n - 1, a - i, b - j, c - k)
              
  dp[n][a][b][c] %= 1000000007

  return dp[n][a][b][c]

print(solve(s, a, b, c))

DP 문제 유형
dp[s][x][y][z] : 곡 s개, a가 x곡, b가 y곡, c가 z곡 남았을 때의 경우의 수

즉 x, y, z 는 각 사람들이 불러야 하는 남은 곡의 수

한 곡을 부를 수 있는 경우의 수는
(a, b, c, a b, a c, b c, a b)

  for i in range(2):
      for j in range(2):
          for k in range(2):
              if i + j + k == 0:
                  continue
              dp[n][a][b][c] += solve(n - 1, a - i, b - j, c - k)

이 코드는 다음 코드와 동일하다.

dp[n][a][b][c] += solve(n - 1, a - 1, b, c) // a만 부르는 경우
dp[n][a][b][c] += solve(n - 1, a, b - 1, c) // b만 부르는 경우
dp[n][a][b][c] += solve(n - 1, a, b, c - 1) // c만 부르는 경우
dp[n][a][b][c] += solve(n - 1, a - 1, b - 1, c) // a, b가 부르는 경우
dp[n][a][b][c] += solve(n - 1, a - 1, b, c - 1) // a, c가 부르는 경우
dp[n][a][b][c] += solve(n - 1, a, b - 1, c - 1) // b, c가 부르는 경우
dp[n][a][b][c] += solve(n - 1, a - 1, b - 1, c - 1) // a, b, c가 부르는 경우

각각의 경우의 수를 모두 재귀호출한 후, 중복은 메모이제이션으로 없앤다.

어렵다 이해하는 데 엄청 오래 걸렸다
아직도 헷갈리는 듯하지만

이게 71퍼의 정답률 문제라니
,,,