[JAVA]백준 2758번: 로또

www.acmicpc.net/problem/2758

2758번: 로또

1. 문제 설명

 

선영이가 매주 로또를 산다. 로또는 1부터 m까지의 숫자 중에서 n개의 수를 고르는 것이다.

 

수를 고를 때, 이전에 고른 수보다 적어도 2배가 되도록 고른다. n과 m이 주어졌을 때 선영이가 구매하는 로또의 개수를 구하는 문제.

 

2. 풀이

 

다이내믹 프로그래밍을 이용하여 풀 수 있다.

 

dp [X][Y]= X번째 수를 고를 때 1부터 Y까지의 숫자 중에서 선택하는 경우의 수 = dp [X-1][Y/2]+dp [X][Y-1]

 

X번째 수를 고를 때 1부터 Y까지의 숫자 중에서 선택하는 경우의 수는 X번째 수를 고를 때 1부터 Y-1까지의 숫자 중에서 선택하는 경우와 X번째 수를 Y로 선택하는 경우 2가지로 나뉜다.

 

X번째 수를 고를 때 1부터 Y-1까지의 숫자 중에서 선택하는 경우는 dp [X][Y-1]이고,

 

X번째 수를 Y로 선택하는 경우는 dp [X-1][Y/2]이다. (이전에 고른 수보다 2배가 커야지만 선택할 수 있기에! 바꿔 말하면 이전의 수는 현재 수의 1/2보다 작아야 한다.)

 

오버플로우가 발생하지 않도록 dp 배열은 long으로 정의하였다.

 

시간 복잡도 : O(TNM) (T: 테스트 케이스)

 

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int x = 0; x < test_case; x++) {
            int lotto_num,lotto_max;

            StringTokenizer st = new StringTokenizer(br.readLine());

            lotto_num = Integer.parseInt(st.nextToken());
            lotto_max = Integer.parseInt(st.nextToken());

            long[][] dp = new long[lotto_num + 1][lotto_max + 1];

            for (int k = 0; k <= lotto_max; k++) {
                dp[0][k] = 1L;
            }

            for (int y = 1; y <= lotto_num; y++) {

                for (int z = 1; z <= lotto_max; z++) {
                    dp[y][z] = dp[y - 1][z / 2] + dp[y][z - 1];
                }
            }

            bw.write(String.valueOf(dp[lotto_num][lotto_max]) + "\n");
        }


        bw.flush();
        bw.close();
        br.close();

    }







}