[백준/9184] 신나는 함수 실행 (with 파이썬)

✔ 문제

---

✔ 풀이

👽 시간 초과 - 재귀함수

import sys
input = sys.stdin.readline

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    elif a < b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        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)

while True:
    a, b, c = map(int, input().split())

    if a == -1 and b == -1 and c == -1:
        break

    res = w(a, b, c)
    print("w({}, {}, {}) = {}".format(a, b, c, res))

 

 

🌱 시간초과 - dp

import sys
input = sys.stdin.readline

MAX = 21
dp = [[[0] * MAX for _ in range(MAX)] for _ in range(MAX)]

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:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]
    else:
        dp[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 dp[a][b][c]

while True:
    a, b, c = map(int, input().split())

    if a == -1 and b == -1 and c == -1:
        break

    res = w(a, b, c)
    print("w({}, {}, {}) = {}".format(a, b, c, res))

MAX = 21인 이유

1,2번째 if문 조건을 보면 a,b,c의 범위가 0~19까지임을 알 수 있음

 

 

💚 dp 풀이2

import sys
input = sys.stdin.readline

MAX = 21
dp = [[[0] * MAX for _ in range(MAX)] for _ in range(MAX)]

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 dp[a][b][c]: #추가
        return dp[a][b][c]
    if a < b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]
    else:
        dp[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 dp[a][b][c]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    print("w({}, {}, {}) = {}".format(a, b, c, w(a, b, c)))

---

✔ 후기

문제에 재귀로 나와있길래 재귀로 풀었다가 역시나 시간초과로 실패,

dp로 풀어보는데 MAX 범위 잡느라 잠깐 멈칫한 상태로 고민하고 풀었지만 시간초과로 실패

도저히 모르겠어서 구글링했더니 if문을 하나 추가하니까 엄청 빠르게 문제가 풀렸다.

 

해당 조건문은 dp[a][b][c]의 값이 존재한다면 (0이면 다른 if문에 걸렸을테니) dp[a][b][c] 값을 그대로 리턴하라는 문장이다.