728x90
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] 부분)
'STUDY > Algorithm' 카테고리의 다른 글
[백준] 9461 파도반 수열 (0) | 2021.03.23 |
---|---|
[백준] 1904 01타일 (0) | 2021.03.23 |
[백준] 17298 오큰수 python (0) | 2021.03.18 |
[SWEA] 1767 프로세서 연결하기 python (0) | 2021.03.17 |
[SWEA] 4013 특이한자석 (0) | 2021.03.16 |