HoonK212 GitHub_Blog

[오늘의 백준] 21번째

19 Mar 2024

“9184번”

백준 알고리즘 스터디

  • 다이나믹 프로그래밍
  • 재귀

문제 : 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력 : 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력 : 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한 : -50 ≤ a, b, c ≤ 50

풀이

import sys
input = sys.stdin.readline

# 동적 프로그래밍을 통해 w(a, b, c)의 결과를 저장할 3차원 리스트 dp를 생성하고, 모든 원소를 1로 초기화 (인덱스 범위는 0에서 20까지로 설정)
dp = [[[1 for x in range(21)] for y in range(21)] for z in range(21)]

# 반복의 기준이 되는 차원의 순서에 주의
for z in range(1, 21):
  for y in range(1, 21):
    for x in range(1, 21):
      if x < y < z: # a < b < c인 경우, w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)로 값을 변경
        dp[x][y][z] = dp[x][y][z - 1] + dp[x][y - 1][z - 1] - dp[x][y - 1][z]
      else: # 그 외의 경우, w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)로 값을 변경
        dp[x][y][z] = dp[x - 1][y][z] + dp[x - 1][y - 1][z] + dp[x - 1][y][z - 1] - dp[x - 1][y - 1][z - 1]

while True:
  a, b, c = map(int, input().split())
  if a == -1 and b == -1 and c == -1: # 입력된 값이 모두 -1인 경우, 루프 종료
    break
  elif a <= 0 or b <= 0 or c <= 0: # a, b, c 중 하나라도 0 이하인 경우, "w(a, b, c) = 1"을 출력
    print("w({0}, {1}, {2}) = 1".format(a, b, c))
  elif a > 20 or b > 20 or c > 20: # a, b, c 중 하나라도 20을 초과하는 경우, 사전에 계산된 w(20, 20, 20)의 값인 1048576을 출력
    print("w({0}, {1}, {2}) = 1048576".format(a, b, c))
  else: # 그 외의 경우, dp 리스트에서 해당하는 값을 찾아 출력
    print("w({0}, {1}, {2}) = {3}".format(a, b, c, dp[a][b][c]))

Related posts