2775번(부녀회장이 될거야)

첫 시도

• 누적합을 사용하면 쉽게 풀 수 있음
• int[14][14] 배열에 인원 합을 계산해 한번만 저장해 주면 이후로 계속 사용 가능
• 시간복잡도는 기껏해야 O((N^2)*T)
• dp[i][j] = dp[i][j-1] + dp[i-1][j];

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] dp;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int[][] arr = new int[15][15];
        int sum = 0;
        for(int i = 1; i<15; i++){
            arr[0][i] = i;
            arr[i][1] = 1;
        }

        for(int i = 1; i<15; i++){
            for(int j =1; j<15; j++){
                arr[i][j] = arr[i][j-1]+ arr[i-1][j];
            }
        }

        for (int i = 0; i < T; i++) {
            int K = Integer.parseInt(br.readLine());
            int N = Integer.parseInt(br.readLine());
            System.out.println(arr[K][N]);
        }
    }
}

참고

• 직접구현