Java : 조합 (Memoization)

문제

풀이

기본적인 풀이

  static int dfs(int n, int r) {
    if (n == r || r == 0) return 1;

    return dfs(n - 1, r - 1) + dfs(n - 1, r);
  }

• 조합의 성질에 따라 n == r 이거나 r == 0일 경우 1을 반환한다.
• 문제에서 주어진 공식대로 dfs를 돌려서 최종 값을 출력한다.

메모이제이션

• 위 방법은 이미 한번 계산한 값을 다시 계산하므로 비효율적이다.
• 한번 계산한 값은 ch[n][r]에 담아서 필요하면 바로 불러다 쓸 수 있게 한다.

  static int dfsMemo(int n, int r) {
    if (n == r || r == 0) return 1;
    if (ch[n][r] > 0) return ch[n][r];

    ch[n][r] = dfsMemo(n - 1, r - 1) + dfsMemo(n - 1, r);
    return ch[n][r];
  }

전체 코드

package inflearn;

import java.util.Scanner;

public class I0807 {
  static int ans;
  static int[][] ch;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int r = sc.nextInt();

    ch = new int[34][34];

    ans = dfsMemo(n, r);
    System.out.println(ans);
  }


  static int dfsMemo(int n, int r) {
    if (n == r || r == 0) return 1;
    if (ch[n][r] > 0) return ch[n][r];

    ch[n][r] = dfsMemo(n - 1, r - 1) + dfsMemo(n - 1, r);
    return ch[n][r];
  }

  static int dfs(int n, int r) {
    if (n == r || r == 0) return 1;

    return dfs(n - 1, r - 1) + dfs(n - 1, r);
  }
}