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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| import java.io.*;
import java.util.*;
class Main {
static int[][][] D;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// a, b, c 중 하나라도 20이 넘어갈 경우
// w(20, 20, 20)을 호출하기 때문에 배열의 범위는 21까지가 최대이다.
D = new int[21][21][21];
int a = 0;
int b = 0;
int c = 0;
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
if(a == -1 && b == -1 && c == -1) {
break;
}
int result = w(a, b, c);
bw.write("w("+a+", "+b+", "+c+") = "+result+"\n");
}
bw.close();
br.close();
}
static int w(int a, int b, int c) {
// 메모이제이션 활용하여 재계산하지 않고 바로 반환
// a, b, c의 범위가 0 <= 20 이어야 하기 때문에 메모이제이션 조건 추가
if((0<=a && a<=20 && 0<=b && b<=20 && 0<=c && c<=20) && (D[a][b][c] != 0)) {
return D[a][b][c];
}
if(a<=0 || b<=0 || c<=0) {
return 1;
}
// a, b, c 중 하나라도 20이 넘어갈 경우
// 배열의 마지막인 D[20][20][20]에 w(20,20,20)을 저장
if(a>20 || b>20 || c>20) {
return D[20][20][20] = w(20, 20, 20);
}
if(a<b && b<c) {
return D[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
}
return D[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);
}
}
|
