자바 - 백준 2758 / 로또

https://www.acmicpc.net/problem/2758

골드4

구현 방법

N = 뽑아야 하는 개수

M = 최대 수

 

1. 완전 탐색 - 시간 초과

처음에 현재 뽑은 수의 두배 이상의 수를 선택해야 하기 때문에 재귀를 이용하면 시간 복잡도가 O(n * log m)이라고 착각했다. 

하지만 실제 시간 복잡도는 O(m * 2^n)를 가진다. 이분 탐색처럼 반틈만 탐색하는게 아니기 때문이다.

 

2. 삼중 포문을 사용한 DP

1번의 문제점은 같은 계산이 반복적으로 이루어진다는 문제점이 있다.

예를 들어서 1에서 재귀가 나누어지면 다음에는 두배인 2부터 2000까지의 재귀가 발생한다.

다음 재귀인 2에서 재귀가 나누어지면 다음에는 두배인 4부터 2000까지의 재귀가 발생한다.

이 두 경우를 보더라도 4 ~ 2000이 겹치게 된다. 

 

그럼 이 겹치는 부분은 계산을 하지 않고 미리 저장하여 중복 계산을 피하면 시간초과 문제가 해결될 것이다. 

이런 이유로 DP 알고리즘을 적용하기로 했다.

문제를 보면 다음과 같은 규칙이 있다.

만약 1 ~ m까지의 수가 있고, n개를 문제 조건과 같이 선택한다고 하자.

이 경우 2배를 해서 m보다 작은 수가 되려면 1 ~ m / 2의 숫자가 있다.

이를 다시 말하면 (n -1)를 선택한 상황에서 1 ~ m / 2의 숫자를 선택하면 곱하기 2를 했을 때 모두 m을 선택할 수 있다는 뜻이 된다.

이를 식으로 나타내면 아래와 같다.

dp[n][m] == n개의 숫자를 선택하고, 선택한 마지막 수는 m이다.

dp[n][m] = dp[n - 1][1]  + ... + dp[n - 1][m / 2] 가 된다.

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

 

이를 통해 아래 조건을 만족하는 경우의 수를 구할 수 있다.

1부터 m까지 숫자 중에 n개의 수를 고르자.

이 때, 각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고르기

=> dp[n][1] + ... + dp[n][m]

long result = 0;
for(int j = 1; j <= m; j++)
    result += dp[n][j];

 

3. 이중 포문을 사용한 DP

2번의 방법을 보면 마지막에 뽑은 수에 대한 개수만 저장되어 있다. 따라서 마지막에 모든 경우의 수를 구하기 위해 한번더 더하는 과정이 필요하다. 이는 누적합을 통해 최적화를 할 수 있다. 구해야 하는 수마다  1 ~ (구해야 하는 수  / 2)를 전부 탐색하는 것이 아니고, 미리 누적을 시키는 것이다.

다시말해 dp[i][j] += dp[i - 1][k], k = 1 부터 m / 2를 하지 말고, dp[i][j] += dp[i][j - 1] + dp[i - 1][j / 2]로 하는 것이다.

여기서 dp[i][j - 1]은 1 ~ (j - 1) / 2를 뜻하기 때문에, 1 ~ (구해야 하는 수  / 2)를 탐색하는 포문을 하나 줄일 수 있다.

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

 

코드

1. 완전 탐색 - 시간 초과

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

/**
* 백준 2758
* 로또
* 골드4
* https://www.acmicpc.net/problem/2758
*/
public class Boj2758 {

    private static int cnt;
    private static int n;
    private static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        for(int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            cnt = 0;
            n = Integer.parseInt(st.nextToken()); // 뽑아야 하는 개수
            m = Integer.parseInt(st.nextToken()); // 최대 수

            combi(1, 1);

            sb.append(cnt).append("\n");
        }

        System.out.print(sb);
    }

    public static void combi(int cur, int count) {
        if(m < cur)
            return;

        if(count == n) {
            cnt++;
            return;
        }

        for(int i = cur * 2; i <= m; i++) {
            combi(i, count + 1);
        }
    }
}

2. 삼중 포문 사용한 DP

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

/**
 * 백준 2758
 * 로또
 * 골드4
 * https://www.acmicpc.net/problem/2758
 */
public class Boj2758 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

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

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

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

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

            int n = Integer.parseInt(st.nextToken()); // 뽑아야 하는 개수
            int m = Integer.parseInt(st.nextToken()); // 최대 수

            long result = 0;
            for(int j = 1; j <= m; j++)
                result += dp[n][j];

            sb.append(result).append("\n");
        }

        System.out.print(sb);
    }
}

3. 이중 포문 사용한 DP

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

/**
 * 백준 2758
 * 로또
 * 골드4
 * https://www.acmicpc.net/problem/2758
 */
public class Boj2758 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

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

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

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

        for(int t = 0; t < T; t++) {
            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.print(sb);
    }
}