백준 2758[자바] java 로또

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

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으로 이루어져 있다.

▶출력

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

▶해설

DP 문제입니다. 조건을 먼저 보겠습니다. 

1. n개의 로또를 사지만 다음 로또 번호는 전꺼보다 2배 커야한다.

2. 마지막 로또 번호가 m보다 작거나 같아도 된다.

 

따라서 어떠한 수를 골랐을 때 다음 수는 2배인 수부터 m까지 고를 수 있습니다. 

예시로 보겠습니다.

n =3 m = 7로 예시를 보겠습니다. 

첫 번째 숫자들은 모두 선택할 수 있습니다.

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2
3

두 번째 숫자는 첫 번째 숫자가 0이 아니라면 그 index*2부터 m까지 첫 번째 숫자의 값을 더해줍니다.

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	0	1	1	2	2	3	3
3

세 번째 숫자도 마찬가지입니다.

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	0	1	1	2	2	3	3
3	0	0	0	1	1	2	2

 

아래와 같은 점화식이 완성됩니다.

for(int j=2; j<=10; j++){
    for(int k=1; k<=4000;k++){
        if(dp[j-1][k]!=0){
            for(int q =k*2; q<=4000; q++){
                dp[j][q] += dp[j-1][k];
            }
        }
    }
}

 

그렇다면 답은 3개의 로또 번호를 골랐을 때 dp [3][j]에 관한 값들을 더해주면 됩니다. 

for(int k=1; k<=m; k++){
    result+=dp[n][k];
}

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

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());

        int n, m;
        long result=0;
        long [][] dp = new long [11][4001];

        for(int j=1; j<=4000; j++){
            dp[1][j] = 1;
        }

        for(int j=2; j<=10; j++){
            for(int k=1; k<=4000;k++){
                if(dp[j-1][k]!=0){
                    for(int q =k*2; q<=4000; q++){
                        dp[j][q] += dp[j-1][k];
                    }
                }
            }
        }
        for(int i=0; i<t; i++){
            String[] s = br.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            result=0;
            for(int k=1; k<=m; k++){
                result+=dp[n][k];
            }
            System.out.println(result);
        }
    }
}