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()
ps/problems/boj/9184.txt · 마지막으로 수정됨: 2022/01/27 02:21 저자 teferi
                
                
토론