[BOJ] 9184 신나는 함수 실행 - JAVA

1. 문제

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

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, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

---

2. 풀이

메인함수

• w값을 저장할 3차원 배열을 만들었다. 어차피 20이 넘어가거나 0이하이면 필요없으므로 21칸만 만들었다. (숫자를 편하게 쓰려고 메모리+1칸을 했다.) DP문제에서는 이 배열이 핵심이다. 이전값을 다시 계산할 필요 없도록 저장해놓고 다음 값에 활용하기 때문이다.
• -1 -1 -1이 들어오기전까지 반복한다. 이 경우가 아니라면 funcW(a,b,c)를 출력한다.

static int[][][] w = new int[21][21][21];
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;
   StringBuilder sb = new StringBuilder();
   String line;

   while(!(line=in.readLine()).equals("-1 -1 -1")){
      st = new StringTokenizer(line);

      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(funcW(a,b,c)).append("\n");
   }
   System.out.print(sb);
}

 

funcW - 재귀함수

• a,b,c 중 0보다 작은 게 있다면 1을 반환한다.
• a,b,c 중 20보다 큰 게 있다면 funcW(20,20,20)을 반환한다.
• 만약 w[a][b][c]에 저장된 값이 있다면 그 값을 반환한다.
• a<b<c라면 funcW(a,b,c-1)+funcW(a,b-1,c-1)-funcW(a,b-1,c) 값을 계산해서 w[a][b][c]에 넣은 후 그대로 반환한다.
• 그 밖의 경우는 funcW(a-1,b,c)+funcW(a-1,b-1,c)+funcW(a-1,b,c-1)-funcW(a-1,b-1,c-1) 값을 계산해서 w[a][b][c]에 넣은 후 그대로 반환한다.

private static int funcW(int a, int b, int c) {
   if(a<=0 || b<=0 || c<=0) return 1;
   if(a>20 || b>20 || c>20) return funcW(20,20,20);
   if(w[a][b][c]!=0) return w[a][b][c];

   if(a<b && b<c) return w[a][b][c] = funcW(a,b,c-1)+funcW(a,b-1,c-1)-funcW(a,b-1,c);
   else return w[a][b][c] = funcW(a-1,b,c)+funcW(a-1,b-1,c)+funcW(a-1,b,c-1)-funcW(a-1,b-1,c-1);
}

---

3. 결과

위와 아래가 엄청나게 차이가 난다. 이유는 String.format() 함수때문이다. 자세한 이유는 이 글에서 설명했다.