[BOJ] 11560 - 다항식 게임 (Java)

알고리즘

• 다이나믹 프로그래밍

1. 문제

• T번의 테스트 케이스에 대해 다항식 p(x)를 계산하고, x^n의 계수를 출력하는 문제
  

2. Idea

• 지수가 1~20인 다항식의 계수를 미리 계산하여 배열에 저장

3. 풀이

3.1. solve 메소드 구현

• 재귀적으로 호출되며, 다항식 p(x)의 계수를 미리 계산하여 dp 배열에 저장한다.
• idx가 20을 초과하면 재귀를 종료(k값의 기준이 20 이하이기 때문)
• 이중 while 루프를 통해 이전 다항식의 계수를 가져와서 현재 다항식의 계수를 갱신
  • idx를 1 증가시키고 다시 solve 메서드를 호출

private static void solve(int idx) {
  if (idx > 20) {
  	return;
  }
  int i = 0;
  while (dp[idx - 1][i] != 0) {
    long nowCoe = dp[idx - 1][i];
    for (int root = 0; root <= idx; root++) {
    	int nextRoot = i + root;
    	dp[idx][nextRoot] += (nowCoe * 1);
    }
    i++;
  }
  solve(idx + 1);
}

3.2. 변수, dp 배열 생성 및 다항식 계수 계산

• T: 테스트 케이스의 수 T를 입력
• dp[0][0]을 1로 초기화, solve(1) 메서드를 호출하여 지수가 1~20인 다항식의 계수를 미리 계산

Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
dp[0][0] = 1;
solve(1);

3.3. 테스트 케이스 입력 및 결과 출력

• 각 테스트 케이스에 대해 k와 n을 입력 받고, dp[k][n]의 값을 출력

for (int i = 1; i <= T; i++) {
	long k = scanner.nextLong();
	long n = scanner.nextLong();
	System.out.println(dp[(int) k][(int) n]);
}

4. 전체코드

import java.util.*;

public class Main {
    static long[][] dp = new long[25][300];

    private static void solve(int idx) {
        if (idx > 20) {
            return;
        }

        int i = 0;
        while (dp[idx - 1][i] != 0) {
            long nowCoe = dp[idx - 1][i];
            for (int root = 0; root <= idx; root++) {
                int nextRoot = i + root;
                dp[idx][nextRoot] += (nowCoe * 1);
            }
            i++;
        }
        solve(idx + 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        dp[0][0] = 1;
        solve(1);

        for (int i = 1; i <= T; i++) {
            long k = scanner.nextLong();
            long n = scanner.nextLong();
            System.out.println(dp[(int) k][(int) n]);
        }
    }
}