[알고리즘] 백준 - 신나는 함수 실행 ( 9184 )

1. 문제

신나는 함수 실행

2. 접근

1. 문제에서 함수를 구현하는 것은 쉬운데, 시간이 오래걸린다는 점에서 DP를 사용하면 된다는 점은 알수있다

2. 풀이를 보면 d를 3차원으로 초기화한다는 점을 알 수 있다. 특이한 점은 21번을 반복한다는 점이다. 이유는 조건에서 20을 초과하면 w(20,20,20)으로 재귀를 하기 때문이다.

3. 조건은 그대로 쓰면 되는데 시간을 좀 더 빠르게 나오게 하기 위해서 중간에 구현된 d[a][b][c] 가 있다면 바로 return하는 것을 볼 수 있다. 또한, 앞의 조건 2개는 바로 return 하는 반면 아래 2개 조건은 d[a][b][c]의 값으로 실행된다는것을 알아야 한다

4. 출력은 format 메소드 쓰면 된다!

 

3. 풀이

# 실버 2 - 9184
import sys
input = sys.stdin.readline


d = [[[0 for _ in range(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
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if d[a][b][c]:  # 이미 실행된 적 있는 애들은 바로 출력하면서 시간 빠르게 하기 위함
        return d[a][b][c]

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