백준 9184 신나는 함수 실행(Java)

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

9184번: 신나는 함수 실행

---

 

해석 및 팁

 

---

 

이 문제는 주어진 함수를 만들면 되지만 시간을 줄이기 위해서 메모이제이션을 활용하면 됩니다. 동일한 계산을 반복할 때 계산한 값을 미리저장해놓고 불러오면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int[][][] arr = new int[21][21][21];
  static StringBuilder sb;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    while(true) {
      sb = new StringBuilder();
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      if(a == -1 && b == -1 && c == -1) break;
      sb.append("w("+a+", "+b+", "+c+") = ").append(w(a, b, c));
      
      System.out.println(sb);
    }
  }

  public static int w(int a, int b, int c) {
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a > 20 || b > 20 || c > 20) return arr[20][20][20] = w(20, 20, 20);
    if(arr[a][b][c] != 0) return arr[a][b][c];
    if(a < b && b < c) return arr[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    return arr[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);
  }
  
}