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
토론