9184 신나는 함수 실행 _python

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

재귀호출만 생각하면 컴퓨터가 멈출것 같아 신이 난다! 아닌가요?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

2가지 방법으로 풀었다. 시간은 둘다 비슷하게 나왔다.

첫번째 방법은 문제에서 주어진 함수를 그대로 사용해서 dp만 추가해주는 방식이다.

연산한 결과를 dp에 저장해두고 같은 값을 여러번 반복하지않도록 dp[a][b][c]에 저장해두는 방식.

완전 그대로만 사용하면 안되고 if문을 하나 더 추가해야한다.

 

두번째방법은 미리 모든 경우를 확인하고 푸는 방법이다.

범위가 많지가 않으니 미리 정답을 구해둘수가 있다. 21*21*21번.

3중 for문으로 모든값을 미리 확인하면 된다.

조건에서 +1번째를 확인하는 경우가 없으므로 충분히 가능하다.

대신 w함수에 있는 0보다 작을때와 20보다 클때는 출력문에서 체크해줘야 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드 1(w함수를 그대로 사용하는 방법)

from collections import deque
import sys
input = sys.stdin.readline

"""

"""

# w함수를 그대로 사용하는 방법
dp = [[[0]*21 for _ in range(21)] for _ in range(21)]
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(f"w({a}, {b}, {c}) = {w(a,b,c)}")

120ms

 

 

 

 

 

 

 

 

 

 

 

 

 

코드 2(미리 모든 경우를 확인해두고 푸는 방법)

from collections import deque
import sys
input = sys.stdin.readline

"""

"""

미리 모든 경우를 확인해두고 푸는 방법
dp = [[[0]*21 for i in range(21)]for i in range(21)]
for a in range(21):
    for b in range(21):
        for c in range(21):
            if a==0 or b==0 or c==0:
                dp[a][b][c] = 1
            elif a<b<c:
                dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c]
            else:
                dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1]

while True:
    a,b,c = map(int,input().split())
    if a==b==c==-1:
        break
    elif a<=0 or b<=0 or c<=0:
        print(f"w({a}, {b}, {c}) = 1")
    elif a>20 or b>20 or c>20:
        print(f"w({a}, {b}, {c}) = {dp[20][20][20]}")
    else:
        print(f"w({a}, {b}, {c}) = {dp[a][b][c]}")

124ms