728x90
1. 문제 설명
재귀 함수 w(a, b, c)가 있는데 이 함수를 구현하는 것은 쉽다! 하지만 그대로 구현하면 값을 구하는데 오래 걸린다.
a, b, c가 주어졌을 때 w(a, b, c)를 출력하라.
2. 풀이
w(a,b,c) 함수의 구현과 메모이제이션을 합쳐서 구현하면 쉽게 풀 수 있는 문제이다.
a, b, c가 주어졌을 때 그 계산의 결과를 dp [a][b][c]에 저장해 두고
다음 a, b, c가 주어졌을 때 똑같은 배열을 재사용하여 이미 계산한 값이면 계산을 수행하지 않는다.
3. 코드
import java.io.*;
import java.util.*;
public class Main {
public static int[][][] dp=new int[21][21][21];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
int a,b,c;
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;
bw.write("w("+String.valueOf(a)+", "+String.valueOf(b)+", "+String.valueOf(c)+") = "+String.valueOf(W_make(a,b,c))+"\n");
}
bw.flush();
bw.close();
br.close();
}
public static int W_make(int a,int b,int c){
if(a<=0 || b<=0 || c<=0)
return 1;
if(a>20 || b>20 || c>20)
return W_make(20,20,20);
if(dp[a][b][c]!=0)
return dp[a][b][c];
if(a<b && b<c)
dp[a][b][c]=W_make(a,b,c-1)+W_make(a,b-1,c-1)-W_make(a,b-1,c);
else
dp[a][b][c]=W_make(a-1,b,c)+W_make(a-1,b-1,c)+W_make(a-1,b,c-1)-W_make(a-1,b-1,c-1);
return dp[a][b][c];
}
}
728x90
'알고리즘' 카테고리의 다른 글
[JAVA]백준 2056번: 작업 (0) | 2021.02.25 |
---|---|
[JAVA]백준 14567번: 선수과목 (Prerequisite) (0) | 2021.02.22 |
[JAVA]백준 13549번: 숨바꼭질 3 (0) | 2021.02.19 |
[JAVA]백준 12851번: 숨바꼭질 2 (0) | 2021.02.18 |
[JAVA]백준 2293번: 동전 1 (0) | 2021.02.15 |