BOJ/백준-9184-python

문제📖

풀이🙏

• 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다.
• 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
• 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력하라.
• DP 알고리즘 문제이다.
• dp 문제를 풀 땐, 미리 배열을 할당해놓은 뒤, 푸는 방식이 수월하고좋다.

코드💻

# boj, 9184 : 신나는 함수 실행, python
# DP algorithm : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
import sys

def w(a, b, c):
    if any((a <= 0, b <= 0, c <= 0)):
        return 1
    elif any((a > 20, b > 20, c > 20)):
        return w(20, 20, 20)

    if dp[a][b][c] :
        return dp[a][b][c]

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

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

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

결과😎

출처 && 깃허브📝

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