[다이나믹 프로그래밍] ▲ 9184번 - 신나는 함수 실행

[백준] 9184번 - 신나는 함수 실행

(한줄평) 재귀함수 그대로 구현하면 되지만 오류를 스스로 해결하지 못했던 문제..! 꼭 복습이 필요하다~

풀이 시간: 60분 이내

1) 문제 해결 아이디어

이 문제는 a, b, c가 주어졌을 때 w(a, b, c)를 구하는 문제다. 이 문제는 아래의 재귀함수 그대로 구현을 하면 되지만 이렇게만 구현하게 되면 동일한 작업을 계속 반복하게 되어 그 값을 구하는데 매우 오랜 시간이 걸리게 되는 문제가 발생한다. 그래서 다이나믹 프로그래밍으로 해결해야하는데 다이나믹 프로그래밍의 핵심은 반복되는 계산을 피하기 위해서 dp테이블에 계산한 값을 저장해두고 나중에 그 값이 필요하다면 바로 그 값을 가져다 쓰는 것이다.

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, b, c 3가지 값에 대한 w(a, b, c)를 기록하기 위한 dp테이블(d)를 (21 * 21 * 21) 크기의 3차원 리스트로 0으로 초기화하여 생성한다. 

w 함수는 위에 조건 그대로 코드를 작성한다.

다만 w(a, b, c)를 호출했을 떄 dp 테이블(d)에 그 값이 기록되어있다면 굳이 w(a, b, c)를 호출할 필요없이 기록된 값을 읽어와 바로 값을 리턴하면 된다.

 

Q. w(a, b, c) 값을 기록하는 dp 테이블을 (21 * 21 * 21) 3차원 리스트로 생성하는 이유는?

처음에 a, b, c가 -50이상 50이하라는 조건을 보고 단순하게 (101 * 101 * 101) 크기의 3차원 배열을 생성해야겠다고 생각했다. 하지만 굳이 이런 사이즈로 생성할 필요가 없는게 2번째 조건(a > 20 or b > 20 or c > 20)을 만족할 때 무조건 w(20, 20, 20)을 리턴한다는 점때문이다. 즉 a , b, c 중 하나라도 20보다 큰 숫자라면 나머지 값과는 상관없이 d[20][20][20]의 값이 필요하다는 것이다.

 

첫번쨰 오류. 틀렸습니다

주어진 예제는 맞게 나왔는데 제출하니까 7%정도까지 되다가 틀렸습니다가 떴다.

처음에는 출력하는 코드를 아래처럼 %연산자를 이용하여 출력했는데, 아마 %d의 범위를 넘어갔을 때 문제가 생기지 않았나 싶다. 안전하게 % 포맷팅 방식 대신에 f-string 문법을 이용하여 출력하는 것이 좋을 듯 하다!!

print("w{%d, %d, %d} = %d" %(a, b, c, res))	# 틀린 코드
print(f'w({a}, {b}, {c}) = {res}')	# 정답 코드

[참고] https://hyjykelly.tistory.com/65

[Python] 문자열 포맷팅하는 3가지 방법

 

두번쨰 오류. 시간초과

이번엔 10% 정도까지 되다가 시간초과가 떴다. 

도저히 어디서 시간초과가 나는지 모르겠어서 다른 코드를 찾아보다가 해답을 찾았다.

while문 내에서 입력값이 들어올 때마다 dp 테이블을 새로 생성한 것이 시간초과의 원인이었다.

이전 입력값으로 생성된 dp 테이블의 값을 다음 입력값이 들어왔을 떄도 그대로 활용하면 되기 때문에 dp테이블(d)를 지역변수가 아니라 전역변수로 선언하면 해결된다!!

[참고] https://hidemasa.tistory.com/104

[백준/BOJ/알고리즘/파이썬(python)]#9148:신나는 함수 실행[재귀]

 

2) 소스코드

def w(a, b, c):
  if a <= 0 or b <= 0 or c <= 0:
    return 1
  if a > 20 or b > 20 or c > 20:
    return w(20, 20, 20)
  # 기록된 값이 있다면 바로 리턴
  if d[a][b][c]:  return d[a][b][c]
  # 기록된 값이 없다면 계산
  if a < b < c:
    d[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    return d[a][b][c]
  else:
    d[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return d[a][b][c]

d = [[[0] * 21 for _ in range(21)] for _ in range(21)]
while True:
  a, b, c = map(int, input().split())  # - 50이상 50이하
  # 종료 조건
  if a == -1 and b == -1 and c == -1:  break
  # w(a, b, c) 값을 기록하기 위한 dp 테이블
  
  res = w(a, b, c)
  print(f'w({a}, {b}, {c}) = {res}')