테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 신나는 함수 실행 ======

===== 풀이 =====
  * 사실상 점화식이 다 주어진 DP 문제.
  * 20*20*20 테이블을 만들어서 바텀업으로 채워나가도 되지만. 문제에 수도코드가 주어진 만큼 그냥 메모이제이션을 써서 탑다운으로 구현했다.
  * 시간복잡도는 DP테이블을 채우는데에 O(20*20*20), t개의 쿼리를 처리하는데에 O(t).
  * 쿼리가 얼마나 들어오는지 문제에는 안 적혀있는데, 굉장히 많은 수가 들어오는 것 같다. sys.stdin.readline()를 쓰지 않고 input()를 쓸 경우 속도가 매우 느려진다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9184. 신나는 함수 실행".

- Problem link: https://www.acmicpc.net/problem/9184
- Solution link: http://www.teferi.net/ps/problems/boj/9184
"""

import functools
import sys


@functools.cache
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 a < b < c:
        return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
    return (w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) -
            w(a - 1, b - 1, c - 1))


def main():
    while True:
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        if a == b == c == -1:
            break
        print(f'w({a}, {b}, {c}) = {w(a, b, c)}')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_2}}