문제:
재귀 호출만 생각하면 신이 난다! 아닌가요?
다음과 같은 재귀함수 w(a, b, c)가 있다.
위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)
a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.
입력:
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
출력:
입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.
풀이방법:
그냥 이 함수를 재귀로 구성하면 시간초과가 발생하게 된다. 따라서 각 결과를 dp 테이블에 저장함으로써 시간을 단축시키도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
dp= [[[0 for _ in range(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)
temp = dp[a][b][c]
if temp!=0:
return temp
if a < b and b < c:
ans = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
dp[a][b][c]=ans
return ans
else:
ans = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
dp[a][b][c]=ans
return ans
while True:
a,b,c=map(int,input().split())
if a==-1 and b==-1 and c==-1:
break
else:
print("w({}, {}, {}) =".format(a,b,c),w(a,b,c))
|
cs |
문제링크:
9184번: 신나는 함수 실행
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2630. 색종이 만들기 (0) | 2021.04.29 |
|---|---|
| [BOJ]3273. 두 수의 합 (0) | 2021.04.27 |
| [BOJ]2981. 검문 (0) | 2021.04.20 |
| [BOJ]10819. 차이를 최대로 (0) | 2021.02.25 |
| [BOJ]14888. 연산자 끼워넣기 (0) | 2021.02.23 |