[백준] 9184 신나는 함수 실행

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

dp_w = [[[1] * 101 for i in range(101)] for j in range(101)]
for i in range(21):
    for j in range(21):
        for k in range(21):
            if i <= 0 or j <= 0 or k <= 0:
                dp_w[i][j][k] = 1
            elif i < j < k:
                dp_w[i][j][k] = dp_w[i][j][k - 1] + dp_w[i][j - 1][k - 1] - dp_w[i][j - 1][k]
            else:
                dp_w[i][j][k] = dp_w[i - 1][j][k] + dp_w[i - 1][j - 1][k] + dp_w[i - 1][j][k - 1] - dp_w[i - 1][j - 1][
                    k - 1]
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 dp_w[20][20][20] #dp_w[a][b][c] = dp_w[20][20][20]
    else:
        return dp_w[a][b][c]

while True:
    x, y, z = map(int, input().split())

    if x == -1 and y == -1 and z== -1:
        break
    print("w({}, {}, {}) = {}".format(x, y, z, w(x, y, z)))

 

DP 문제를 어떻게 풀어야할지 조금 많이 고민했다.

인자가 세개가 들어가야하므로 3차원 배열을 사용하면 될것같았고 총 범위 -50<= x,y,z<=50에 대한 배열을 잡았다.

범위가 0 이하인 수에 대해서는 1이 나와야하므로 1로 배열을 초기화시켰다.

w함수에 대해서는 사실 이해를 잘 못해서 그냥 붙여넣었고

x,y,z 가 0부터 20 범위내에 있을때 값을 하나씩 변경하며 dp_w의 값을 채워넣었다.

(다시보니 범위 지정을 잘못했다. 0부터 20까지만 구해놓고 나머지에 대해서는 그냥 값이 나오게 하면 되는 건데...)

어쨌든 그렇게해서 구해보니 결과는 나왔다.

---

dp_w = [[[0] * 21 for i in range(21)] for j 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_w[a][b][c]:
        return dp_w[a][b][c]
    if a < b < c:
        dp_w[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp_w[a][b][c]

    dp_w[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_w[a][b][c]

while True:
    x, y, z = map(int, input().split())

    if x == -1 and y == -1 and z== -1:
        break
    print("w({}, {}, {}) = {}".format(x, y, z, w(x, y, z)))

타인의 코드는 재귀도 사용하고 dp도 사용한 코드이다.

배열의 범위도 21까지로 줄였고 0으로 초기화시킨다.

값이 없으면(배열의 값이 0인경우) 재귀를 돌고, 값이 있으면 바로 재귀를 끝내는 코드가 추가가 되어있다.

(if dp_w[a][b][c]: return dp_w[a][b][c] 부분)