[백준 2758] 로또 - JAVA

WTS·2026년 4월 20일

다이나믹 프로그래밍 백준 코딩테스트 코딩테스트스터디

코딩 테스트

목록 보기

63/81

문제 링크는 백준 서비스 종료로 미첨부합니다.

코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!

문제 정의

$1$ ~ $m$ 까지 숫자 중에 $n$ 개의 수를 고르는 로또
- $A[1, 2, 3, 4, 5,.., m]$ 에서 $n$ 개의 숫자 선택하는 로또가 존재
단, 이전 숫자의 최소 2배 이상인 수만 다음 숫자로 고를 수 있음
이런 조건으로 만들 수 있는 조합의 개수를 구하기

간단한 예시

로또 번호의 조합을 보게 되면 같은 숫자들이 중복되는 것을 확인할 수 있습니다.

접근 방법

로또 번호의 조합을 보게 되면 같은 숫자들이 중복되는 것을 확인할 수 있습니다.

이것으로 알 수 있는 사실은
부분 문제의 결과를 DP에 기록해 두면
같은 계산을 반복하지 않고 문제를 해결할 수 있다는 것입니다.

점화식

제가 세운 점화식입니다.

𝒅𝒑[𝒏−𝟏][𝒎/𝟐] (𝒎을 마지막 숫자로 추가할 수 있는 조합의 수)
- $m$ 을 마지막 수로 추가하기 위해서는 이전 수는 𝒎/𝟐이하여야 합니다.
자바의 int타입에 대한 / 연산 특성을 활용해서 𝑚이 짝수이던 홀수이던
𝑚을 마지막 수로 추가할 수 있는 모든 조합을 구할 수 있습니다.
𝒅𝒑[𝒏][𝒎−𝟏] (𝟏 ~ 𝒎−𝟏의 숫자에서 n개의 숫자를 뽑는 모든 조합의 수)
- 마지막 수를 𝒎보다 작은 수 중에서 고른 경우 (즉, 𝒎은 제외한 조합)

추가 설명

첫 번째 행 초기화

숫자 $1$ 개 선택할 때 $1$ ~ $m$ 개 뽑는 경우의 수는 $m$ 이므로
위와 같이 첫 번째 행을 자기 열의 인덱스 값으로 초기화합니다.

열의 인덱스 저장

예시를 들어보자면

이므로 시작 지점을
$N$ 번째 숫자를 선택하기 위해 나올 수 있는 최솟값으로 지정하자는 것입니다.

재사용

이 문제에서는 테스트 케이스에 따라 문제의 결과가 변하지 않습니다.
단지 DP 테이블의 크기에만 변화가 있을 뿐입니다.

그렇기 때문에 문제에서 제시하는 최대 범위로
한 번에 DP 테이블을 채운 후
테스트 케이스별로 DP 테이블에 접근한다면
$O(1)$ 의 시간 복잡도로 정답을 출력할 수 있습니다.

코드

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

public class Main {
    static StringTokenizer st;
    static StringBuilder sb;
    static final int N = 10;
    static final int M = 2000;
    static long[][] dp = new long[N+1][M+1];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        for (int i = 1; i <= M; i++) dp[1][i] = i;

        for (int i = 2; i <= N; i++) {
            for (int j = (int)Math.pow(2, i-1); j <= M; j++) {
                dp[i][j] = dp[i-1][j/2] + dp[i][j-1];
            }
        }

        int T = Integer.parseInt(br.readLine());
        while (T --> 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            sb.append(dp[n][m]).append("\n");
        }
        System.out.println(sb);
    }
}