백준 9184 신나는 함수 실행

❌ 백준 9184 신나는 함수 실행

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

오답.

너무 겁먹었다.

풀고나서 보니 그냥 떠먹여주는 문제인데, 풀기 전에는 정말 어렵게 보였다.

막막한 부분이 몇군데 있었다.

1) 규칙을 찾으려 했다.
수학문제도 아닌데 규칙을 찾으려 했다.
그래서 더 어렵게 느껴졌고, 예시로 숫자 몇개를 집어넣어서 전개할수록 더 큰 벽을 느꼈다.

2) 근거도 없는 걱정.
규칙을 찾으려 하다보니, 어떻게 풀어도 시간초과가 나올것같은 근거도 없고 영양가도 없는 걱정만 머릿속에 가득해졌다.

2) 동적 계획법을 어떻게 적용해야 할지 몰랐다.
힌트를 보고 동적 계획법을 사용해 푸는 문제라는건 알았는데, 어디에 적용해야할지 감이 오지 않았다.
저 함수를 그대로 구현해서 메모이제이션 기능만 붙이면 풀릴거라는 발상에 다다르지 못했다.
안될거라는 생각만 했다.
결국엔 규칙을 찾는데에만 혈안이 되어있었다.

3) 3차원 배열
3차원 배열을 한번도 써본 적이 없었다.
막연한 두려움이 있었다.

어려운 문제를 만나면 알고리즘 처음 시작했을때마냥 막막해지고, 머릿속에서 더러운 풀이방법만 떠오르고, 냉정한 사고가 불가능해진다.

겁먹지말자.

import sys

result = [[[-1 for s in range(21)] for c in range(21)] for v 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 result[a][b][c] != -1 :
        return result[a][b][c]

    if a<b and b<c :
        cal =  w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        result[a][b][c] = cal
        return cal

    cal = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
    result[a][b][c] = cal
    return cal

while True :
    x,y,z = map(int,sys.stdin.readline().split())
    if x==-1 and y == -1 and z == -1 :
        quit()
    print(f'w({x}, {y}, {z}) = {w(x,y,z)}')