#Algorithm
문제 번호
9184번 신나는 함수 실행(S2)
알고리즘 + 이론
DP
정답 코드
# 9184번
# -50<= a,b,c <= 50
# 결국 1을 몇 번 더하냐 이런 느낌인데
# 1 1 1 일 때
# 0 1 1 / 0 0 1 / 0 1 0 / 0 0 0
# 1 + 1 + 1 - 1 = 2
# 2 2 2 일 때
# 1 2 2 + 1 1 2 + 1 2 1 - 1 1 1(2)
# (2) + (2) + (2) - (2) = 4
# 21 * 21 * 21 번 탐색 정도
# 결국 0부터 20까지 DP로 구해서 다 더한 값 찾으면 될듯
# 1 2 3 일 때
# (1) + (1) + (1) - 1 = 2 가 아니라~
# 1 2 2 + 1 1 2 - 1 1 3
# 2 + 2 - 2
w = [0 for _ in range(9261)]
for a in range(21):
for b in range(21):
for c in range(21):
if a == 0 or b == 0 or c == 0:
w[a*441+b*21+c] = 1
continue
elif a < b and b < c:
w[a*441+b*21+c] = w[a*441+b*21+c-1] + w[a*441+(b-1)*21+c-1] - w[a*441+(b-1)*21+c]
continue
w[a*441+b*21+c] = w[(a-1)*441+b*21+c] + w[(a-1)*441+(b-1)*21+c] + w[(a-1)*441+b*21+c-1] - w[(a-1)*441+(b-1)*21+c-1]
result = []
while True:
a,b,c = map(int,input().split())
if a == -1 and b == -1 and c == -1:
break
temp = [a,b,c]
if a <= 0 or b <= 0 or c <= 0:
a = 0; b = 0; c = 0
elif a > 20 or b > 20 or c > 20:
a = 20; b = 20; c = 20
temp.append(w[a*441+b*21+c])
result.append(temp)
for i in result:
print(f'w({i[0]}, {i[1]}, {i[2]}) = {i[3]}')
느낀점 & 피드백
DP 코드는 빠르게 짰는데 세세한 조건 분기들에서 거의 2시간 걸렸다.
조건을 잘 보고 반례랑 테스트 케이스를 잘 정해서 해봐야할 것 같다,
이 글이 도움이 되셨나요?