https://www.acmicpc.net/problem/9184
DP문제
문제 코드
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)
문제 이해
문제의 설명대로 위의 코드를 그대로 제출하면 a=15, b=15, c15와 같은 값을 대입하면
a-1이 0이 될 때까지 실행된 노드 수만큼 a-1, a-1, b-1,.. 실행 a-1, b-1을 실행하며 생성된 노드 수만큼
다른 재귀 호출들을 실행하며 많은 중복 연산을 실행하여 시간 내에 값을 도출해 낼 수가 없음
접근 1
딕셔너리를 만들어 (a, b, c)를 key로 value에(a, b, c) 계산된 횟수(0이 되면 return이 1이므로)를 저장하여
(a, b, c) 이하의 계산은 하지 않는 식으로 하려 했으나
구현이 잘되지 않고 횟수를 저장할 마땅한 방법이 떠오르지 않음
답지 확인
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 array[a][b][c]:
return array[a][b][c]
if a < b < c:
array[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return array[a][b][c]
array[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 array[a][b][c]
array = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
while True:
a, b, c = map(int, input().split())
if a==-1 and b==-1 and c==-1:
break
print(f'w({a}, {b}, {c}) = {w(a,b,c)}')
출저:https://velog.io/@noion0511/%EC%8B%A0%EB%82%98%EB%8A%94-%ED%95%A8%EC%88%98-%EC%8B%A4%ED%96%899184
확인하자마자 횟수를 따로 계산할 이유가 없었는데 너무 짧게 생각했단 걸 느꼈고
확인 후에 다시 코드를 작성할 때 3차원 리스트는 생소하여 원래 사용하려 했던 딕셔너리 사용했고
a, b, c의 범위 체크(0~20)를 하기 전에 딕셔너리에 키 확인 후 반환하는 조건문을 사용하여
불필요한 키 생성이 되어 수정하여 제출함
입력받는 부분에서 리스트에 별도로 추가하지 않고 바로 W를 연산하며 출력하여 좀 더 간결하게
코드를 짤 수 있었는데 이번 문제는 집중을 너무 못한 거 같음
내코드
import sys
input = sys.stdin.readline
ilist = list()
while True:
a,b,c = map(int,input().split())
if a == -1 and b == -1 and c == -1:
break
ilist.append([a,b,c])
savdict = dict()
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 (a,b,c) in savdict.keys(): # 0미만,20초과의 값은 위의 조건문에서 초기화 하여 불필요한 key의 생성을 막음
return savdict[(a,b,c)]
if a < b and b <c:
savdict[(a,b,c)] = W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c)
return W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c)
savdict[(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 savdict[(a,b,c)]
for a,b,c in ilist:
print("w({0}, {1}, {2}) = {3}".format(a,b,c,W(a,b,c)))
결과
내 코드 (딕셔너리 사용)
답지(리스트 사용)
여러 답지를 봤을 때 보통 3차원 리스트를 사용하여 문제를 해결하셨는데
딕셔너리 사용 결과가 시간은 빠른데 메모리를 좀 더 사용했음
해당 문제를 해결할 때 리스트와 딕셔너리의 차이점을 좀 더 알 필요가 있을 거 같음