2758번. 로또

 

아이디어

dp[i][j] 를 1 ~ j 까지 숫자 중 i 개를 문제에서 요구하는 규칙에 따라 뽑을 때 경우의 수라고 정의

 

dp[i][j] 는 1 ~ j / 2 까지 i - 1 개를 뽑고 여기에 j 를 추가하는 케이스들 + 1 ~ j-1 까지 i 개를 뽑은 케이스들의 합이된다.

 

dp[i][j] = dp[i - 1][j / 2] + dp[i][j - 1]

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        long[][] dp = new long[11][2001];

        Arrays.fill(dp[0], 1);

        for (int i = 1; i <= 10; i++) {
            for (int j = 1; j <= 2000; j++) {
                dp[i][j] = dp[i - 1][j / 2] + dp[i][j - 1];
            }
        }

        StringBuilder results = new StringBuilder();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            results.append(dp[n][m]).append("\n");
        }

        System.out.println(results);
    }
}