사용자 도구

사이트 도구


ps:problems:boj:9184

신나는 함수 실행

ps
링크acmicpc.net/…
출처BOJ
문제 번호9184
문제명신나는 함수 실행
레벨실버 2
분류

DP

시간복잡도O(abc+t)
인풋사이즈a<=20, b<=20, c<=20, t<=?
사용한 언어Python
제출기록34000KB / 144ms
최고기록80ms
해결날짜2021/09/06

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
X C U I H
 
ps/problems/boj/9184.txt · 마지막으로 수정됨: 2022/01/27 02:21 저자 teferi