[JAVA]2758 로또(dfs 시간초과/ dp)

📚 문제

2758번: 로또

🔍 아이디어

처음 문제를 봤을 때는 그냥 dfs를 이용하는 풀이를 생각했다 -> 그래서 3번 시간 초과 났다 (dfs에서도 최적화 가능한 줄 알고 여러 번 도전했다.)

3번이나 시간초과 후에는 dp를 떠올렸다. 생각해보니까 가능하다는 생각이 들었다.

그래서 dp로 수정하고 제출하니까 16%에서 틀렸습니다 라는 메시지가 나와서 당황했다.

뭐지.. 설마 타입문제인가 라는 생각으로 엣지 케이스를 넣으니까 음수로 나와서 오버플로우발생을 확인했다 이후에 long으로 선언하여 다시 제출하니까 통과했다.

 

---

문제 자체는 단순 dfs로 접근하면 간단하다.

그 전의 숫자를 저장하고 해당 숫자보다 2배큰 숫자만 가능하도록 dfs를 하면 된다.

private static void dfsCnt(int nowDepth, int start) {
    if (nowDepth == n) {
        cnt++;
    } else {
        for (int i = start; i <= m; i++) {
            dfsCnt(nowDepth + 1, i * 2); //이전 숫자보다 2배 커야한다.
        }
    }
}

근데 이렇게 하면 시간초과가 난다.

생각해보니 start에서 m까지의 범위까지를 반복하는 것보다 만약 m이 10이라면
4 : 10
3 : 10/2
2 : 10/2/2
1 : 10/2/2/2
의 범위내의 숫자여야만 n번까지의 숫자가 로또로 뽑힐 수 있다는 생각이 들었다.

private static void dfsCnt(int nowDepth, int start) {
    if (nowDepth == n) {
        cnt++;
    } else {
        for (int i = start; i <= m / Math.pow(2, n - nowDepth - 1); i++) {
            dfsCnt(nowDepth + 1, i * 2);
        }
    }
}

근데 이렇게 해도 시간 초과가 발생한다.

---

그래서 마지막 풀이인 dp를 사용하였다. 정답

dp에서는 i는 현재까지 뽑은 숫자, j는 해당 범위 : 즉 dp [i][j]는 j까지의 숫자 중 i개를 뽑을 수 있는 경우의 수를 저장하고 있다.

j를 Math.pow(2,i-1)로 지정한 이유는 숫자의 시작이 1부터 이기 때문에 적어도 1/2/4/8/16의 숫서로 증가해 나가서 해당 범위를 지정했다. (생각해 보니까 end범위도 지정할 수 있지 않을까)

 

END 범위를 지정하는 경우

답은 맞는데 시간이 더 걸린다. pow 계산 때문인가 (비트마스킹을 이용하면 더 짧아지나..)

Arrays.fill(dp[1], 1);
dp[1][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = (int) Math.pow(2, i - 1); j <= m / Math.pow(2, n - i); j++) {
        dp[i][j] += dp[i - 1][j / 2]; //현재값 /2보다 작은 모든 경우 i가 나올 수 있음
        dp[i][j] += dp[i][j - 1];
        //누적합 형식을 이용하기위해서 더한다. 이전숫자까지의 가능한 경우의 수를 더한다(더 작은 경우는 가능하기 때문에)
    }
}

 

 

dp[i][j]는 i-1개의 숫자를 j/2개의 범위 안에서 뽑은 경우에 다음 숫자로 j를 뽑을 수 있어서 더한다.

그리고 dp[i][j]는 dp[i][j-1]까지 뽑은 경우도 넣을 수 있음으로 누적합 방식을 이용하기 위하여 더하였다.

Arrays.fill(dp[1], 1);
dp[1][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = (int) Math.pow(2, i - 1); j <= m; j++) {
        dp[i][j] += dp[i - 1][j / 2]; //현재값 /2보다 작은 모든 경우 i가 나올 수 있음
        dp[i][j] += dp[i][j - 1];
        //누적합 형식을 이용하기위해서 더한다. 이전숫자까지의 가능한 경우의 수를 더한다(더 작은 경우는 가능하기 때문에)
    }
}

 

📝 풀이

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

public class Main {

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

        //선영이가 구매하는 로또의 개수를 구하여라
        //이전 숫자보다 두배이상 커야한다.
        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());
            long[][] dp = new long[n + 1][m + 1]; //숫자 m까지 n개의 숫자를 뽑는 경우의 수

            Arrays.fill(dp[1], 1);
            dp[1][0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = (int) Math.pow(2, i - 1); j <= m; j++) {
                    dp[i][j] += dp[i - 1][j / 2]; //현재값 /2보다 작은 모든 경우 i가 나올 수 있음
                    dp[i][j] += dp[i][j - 1];
                    //누적합 형식을 이용하기위해서 더한다. 이전숫자까지의 가능한 경우의 수를 더한다(더 작은 경우는 가능하기 때문에)
                }
            }
            sb.append(dp[n][m]).append("\n");
        }
        System.out.println(sb);
    }
}