[백준 알고리즘 풀이] 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;
    }
  }
}

No comments:

Post a Comment

무한의 세계

무한 집합의 크기 Cardinality , 즉 원소의 개수를 수학에서는 '농도'라고 말한다. 유한 집합의 크기는 그대로 원소의 개수 이지만, 무한 집합의 경우는 원소의 개수를 낱낱이 셈하는 것은 불가능하기 때문에 '농도'라...