[Java] 백준 2758. 로또

📌 문제 링크 - https://www.acmicpc.net/problem/2758

 

 

---

 

 

 

 

문제

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다.

이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 수를 고를 때 각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고르기 때문이다.

예를 들어, n=4, m=10일 때, 선영이는 다음과 같이 고를 수 있다.

• 1 2 4 8
• 1 2 4 9
• 1 2 4 10
• 1 2 5 10

따라서 선영이는 로또를 4개 산다. 

선영이는 돈이 엄청나게 많기 때문에, 수를 고르는 방법의 수 만큼 로또를 구매하며, 같은 방법으로 2장이상 구매하지 않는다.

n과 m이 주어졌을 때, 선영이가 구매하는 로또의 개수를 출력하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n과 m으로 이루어져 있다.

• 1 ≤ n ≤ 10
• 1 ≤ m ≤ 2,000
• n ≤ m

 

 

출력

각 테스트 케이스에 대해 선영이가 로또를 몇 개나 구매하는지 한 줄에 하나씩 출력한다.

 

 

 

 

 

 

---

 

 

풀이

dp로 풀 수 있는 문제다.

dp[n][m] = 1부터 m까지 숫자 중에서 n개를 고르는 방법의 수

 

점화식은 아래와 같다.

dp[n][m] = dp[n-1][m/2] + dp[n][m-1]

 

dp[n-1][m/2]

숫자 m을 선택하는 경우다. 

m을 선택한다면 이전에 고른 숫자는 m/2 이하여야한다. 이는 문제 조건인 '각 숫자는 이전 수의 적어도 2배'를 만족시키기 위해서다.

 

dp[n][m-1]

m을 선택하지 않는 경우다. 이 경우에는 1부터 m-1까지의 숫자 중에서 n개를 고르는 경우의 수를 더해준다.

 

 

 

 

이처럼 dp 배열을 미리 구해놓고, 각 테스트케이스에서 주어진 N과 M에 따라 dp[N][M]을 출력해주면 된다.

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/2758
public class Main_2758 {
    private static final int MAX_N = 11, MAX_M = 2001; // (1 ≤ n ≤ 10), (1 ≤ m ≤ 2,000)
    private static long[][] dp; // 1~m 까지의 숫자 중에서 n개를 고르는 방법의 수


    public static void main(String[] args) throws IOException {
        init();
        sol();
    }//main


    private static void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder ans = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        StringTokenizer st;
        int N, M;

        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // n개의 수를 고르는
            M = Integer.parseInt(st.nextToken()); // 1부터 m까지 숫자 중

            ans.append(dp[N][M]).append('\n');
        }

        br.close();

        System.out.print(ans);
    }//sol


    private static void init() {
        dp = new long[MAX_N][MAX_M]; // 1~m 까지의 숫자 중에서 n개를 고르는 방법의 수

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

        for(int cnt=1; cnt<MAX_N; cnt++) {
            for(int num=1; num<MAX_M; num++) {
                // dp[cnt][num] = num을 고른 경우 + num을 고르지 않은 경우
                dp[cnt][num] = dp[cnt-1][num/2] + dp[cnt][num-1];
            }
        }
    }//init


}//class