🔍 Problem
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)신난다! 아니 전혀 신나지 않는다. 이 문제는 위의 코드를 동적 계획법으로 작성해보라는 문제였다. 동적 프로그래밍에 관한 이론적인 내용은 아래 링크를 확인해보면 될 것이다.
결국 이 문제의 요지는 두번째 if문에 달려있다. 이 코드가 의미하는 것은 만약 a,b,c가 20이 넘으면 다 같은 값으로 처리해 주겠다는 의미이다. 그래서 우리는 50이라는 숫자가 들어와도 (참고로, 50 ≤ a, b, c ≤ 50) w(20..)으로 결국 처리되기 때문에 동적배열의 저장공간을 50까지 생각할 필요가 없고, a,b,c 즉 3차원 배열의 공간을 한 껏 줄일 수 있다. 그렇다면 이제 구현해 볼 차례이다.
📒 해결과정
가. 동적 프로그래밍에 적합한 조건인지 확인해보자.
1. 작은 문제들이 반복적으로 일어나는가?
2. 같은 문제들은 구할 때마다 정답이 모두 같은가?첫 번째는 이 문제가 작은 문제들이 반복적으로 일어나는 부분을 가지고 있느냐이다. 정답은 yes이다. 왜냐하면 w(a,b,c)가 한번만 호출되지 않고 여러번 반복되기 때문이다. 따라서 이것은 동적프로그래밍을 사용해서 리스트에 값을 저장해놓으면 된다. 그리고 우리가 원할때 꺼내서 쓰면 된다. 이로써 시간을 단축할 수 있다. 두번째는 a,b,c 를 상수라고 했을 때, w(a,b,c)는 항상 값이 일정하므로 동적 프로그래밍 조건2를 만족한다. 원하는 값을 리스트에 조건1에서 저장해놓는데 그 값들이 수시로 바뀌면 리스트에 값들을 저장하는 의미가 없다. 따라서 조건2가 무조건 필요하고 이 문제는 이 조건을 만족한다.
나. 리스트(MEMO)에 꺼내오고 저장 할 코드 생각하기
동적 프로그래밍 저장과 꺼내오기의 반복이다. 그렇다면 원하는 값을 리스트의 특정 인덱스에 저장하고 그 값을 리턴해줘야 호출된 부분(아래 코드의 빨간색 부분) 그리고 저장을 동시에 할 수 있다.
if a < b and b < c, then w(a, b, c) returns:
memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return memo[a][b][c]
else:
memo[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 memo[a][b][c]
💻 Code
import sys
memo = [[[0]*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
if a > 20 or b > 20 or c > 20:
return w(20,20,20)
if memo[a][b][c]:
return memo[a][b][c] # ! : DP값이 존재하면 바로 리턴 -> 이게 동적계획법의 핵심
if a < b and b < c:
memo[a][b][c]=w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return memo[a][b][c]
else:
memo[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 memo[a][b][c]
while(True):
a,b,c=map(int, sys.stdin.readline().split())
if a==-1 and b==-1 and c== -1:
break
print(f"w({a},{b},{c}) = {w(a,b,c)}")
🤔 느낀점
해당 코드로 인해 동적계획법 코드를 처음 짜게 되었고 동적계획법이라는 이름을 왜 이렇게 붙혔는지 전혀 이해가 안된다. 나라면 분할저장및출력법이라고 붙일 것이다.
