[Java] 백준 2758번 : 로또 (Top-down, Bottom-up 두 가지 방식 풀이)

문제소개

 

Top-down

첫 번째 시도는 재귀함수를 이용한 memorization 기법을 활용했다.

 

dp[i][j] = i번째로 j를 선택하는 모든 경우의 수

static long findLotto(int depth, int pick) {
        if (depth == N) {
            return 1;
        }
        if (dp[depth][pick] != -1) {
            return dp[depth][pick];
        }
        dp[depth][pick] = 0;
        for (int i = 2 * pick; i * Math.pow(2, N - depth - 1) <= M; i++) {
            dp[depth][pick] += findLotto(depth + 1, i);
        }
        return dp[depth][pick];
}

 

1. 뽑아야 하는 개수 N까지 도달한다면 1가지 경우를 찾았으므로 1을 반환

2. dp배열의 값이 -1이 아니라면 == 이미 방문해서 경우의 수를 알고있다면, 다시 탐색하지 않고 기존 값을 반환

3. 반복문을 돌며 재귀적으로 탐색

 

위와 같은 흐름으로 구성했고, 사실 모든 반례 및 테스트 케이스가 다 맞았지만 16%에서 시간초과가 발생했다.

'이미 시간 초과를 막기 위해서 탐색한 곳이 있다면 재탐색하지 않도록 만들었는데 왜 시간초과...?' 라고 오랜시간 생각했다.

 

결론은 테스트케이스의 짜임새에 있었다.

하나의 테스트케이스에 대해서, N, M의 쌍이 하나만 주어지지 않고 정말 많은 경우로 주어질 수 있다.

이 경우 초기에 짠 코드는 매 (N, M) 쌍 마다 dp 배열을 새롭게 다시 만드는 구조였기 때문에 시간초과가 발생한 것이다.

해결방법은 dp배열을 (N, M) 쌍 마다 다시 만드는 구조가 아닌, 한번 만들어두면 재사용할 수 있도록 변경해야했다.

 

근데 여기서 문제가 있었다.

해당 재귀함수는 (N, M) 쌍이 새롭게 들어올 때마다 dp[][]의 대부분의 값들이 변경되기 때문에 재사용할 수 없었다.

 

그래서 dp[1][1]에 모든 경우의 수를 담는 방식이 아닌, dp[N][M]에 모든 경우의 수를 담는 방식으로 코드를 수정했다.

아래는 전체 코드이다.

package DP.백준2758_로또;

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

public class Main {

    static int T, N, M;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        dp = new long[11][2001];
        Arrays.stream(dp)
                .forEach(arr -> Arrays.fill(arr, -1));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            long result = 0;
            for (int j = M; j / Math.pow(2, N - 1) >= 1; j--) {
                result += findLotto(N, j);
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }

    static long findLotto(int depth, int pick) {
        if (depth == 1) {
            return 1;
        }
        if (dp[depth][pick] != -1) {
            return dp[depth][pick];
        }
        dp[depth][pick] = 0;
        for(int i = pick / 2; i / Math.pow(2, depth - 2) >= 1; i--) {
            dp[depth][pick] += findLotto(depth - 1, i);
        }
        return dp[depth][pick];
    }
}

 

* Top-down으로 풀이한 분들 중 시간초과를 겪는 사람이 많았는데, 어디서 잘못한 것인지 나와있는 게시글을 찾지 못했다.

혹시나 Top-down으로 이 문제를 풀이하다가 시간초과 때문에 어려움을 겪으신다면 도움이 되길 바랍니다,,,

 

Bottom-up

 

반복문을 활용한 Bottom-up 방식으로도 풀이해봤다.

 

dp[i][j] = i번째로 j를 뽑았을 때 가능한 모든 경우의 수

사실 Top-down과 의미하는 바는 동일하다.

하지만 탐색 순서가 반대이다.

 

Top-down은 재귀함수를 통해 가장 뒤에서부터 앞으로, Bottom-up은 반복문을 통해 가장 앞에서부터 뒤로 간다.

점화식은 아래와 같이 표현된다.

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

 

dp[i][j]는 i-1번째에서, 수학적으로 현재 자리에 올 수 있는 숫자들을 j / 2부터 아래로 내려가며 모든 경우의 수들을 더해준 값이다.

초기에 dp[0][0] = 1로 초기화시켜주면 준비는 끝난다.

 

전체 코드는 아래와 같다.

package DP.백준2758_로또;

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

public class Main {

    static int T, N, M;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        dp = new long[11][2001];
        StringBuilder sb = new StringBuilder();

        dp[0][0] = 1;
        for (int i = 1; i <= 10; i++) {
            for (int j = 1; j <= 2000; j++) {
                for (int k = j / 2; k >= 0; k--) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            long result = 0;
            for (int j = M; j >= Math.pow(2, N - 1); j--) {
                result += dp[N][j];
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }

}