[백준 알고리즘 풀이] 9095번 1, 2, 3 더하기

이 문제는 정수론에 integer partition 이라는건데, 추가된 조건은 1, 2, 3으로만 분할하라는 얘기다. 간단하게 iterative 또는 recursive로 완전탐색하는 것으로 구현 가능하다.

import java.util.Scanner;

/*
 * 9095번 1, 2, 3 더하기
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
 
    int tests = sc.nextInt();
 
    for (int i = 0; i < tests; i++) {
      int n = sc.nextInt();
      System.out.println(partition(n));
    }
    sc.close();
  }
 
  private static int partition(int n) {
    if (n == 0) {
      return 1;
    } else if (n < 0) {
      return 0;
    } else {
      int sum = 0;
      for (int i = 3; i > 0; --i) {
        sum += partition(n - i);
      }
      return sum;
    }
  }
}