[Java] BaekJoon 2758. 로또(골드4) (DFS, DP)

문제출처: https://www.acmicpc.net/problem/2758

2758번: 로또

 

문제이해

 

목표

로또를 산다.
로또를 살 때 고르는 숫자는 N개, 그리고 숫자의 범위는 1부터 M까지다. 
각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고른다.
N,M과 주어질 때, 로또를 고르는 방법의 수 만큼 로또를 구매한다.
선양이가 구매하는 로또의 개수를 출력하라

 

풀이

 

첫번째 고안한 풀이 

 

1. 주어진 M을 N만큼 2로 나눠서 각자릿수의 상한 값을 정해준다. 

  ex) N = 4, M = 10 일때 

   ArrayList => 10, 5, 2 ,1이 담긴다. 

• 끝 인덱스의 값(1)부터, 로또의 첫번째 자리는 1이하여야 되고
• 로또의 두번째 자리는 2이하여야 되고
• 로또의 세번째 자리는 5이하여야 되고
• 로또의 네번째 자리는 10이하여야 된다.

이렇게 상한 값을 정하고

 

2.  첫번째 자릿수부터 DFS로 들어가서 구할 수 있는 로또 방법을 구한다. 

이때, DP를 이용하는데,
DP[들어온 자릿수][들어온 값]을 기억하여, 이미 있는 값이면 이를 활용하고 아니면 탐색할 수 있도록 한다. 

 

 

다른 사람의 코드를 본 풀이

 

1. dp를 이용하여 문제를 푼다.
   dp[자릿수][값] => 해당 자릿수에 1부터 해당 값까지의 수로 발생할 수 있는 로또 경우의 수를 의미한다.
   
   
2. 점화식이 있다. 
   

   dp[i][j] = dp[i-1][j/2] + dp[i][j-1];

    
3. [현재 자릿수][현재 번호] = [이전자릿수][현재번호/2] + [현재자릿수][현재번호-1]
   
   ex)
   dp[4][16] = dp[3][8] + dp[4][15]
   dp[3][8] = dp[2][4] + dp[3][7]
   dp[2][4] = dp[1][2] + dp[2][3]
   dp[1][2] = dp[0][1] + dp[1][1]
   dp[0][1] = 1
4. 예시
   dp[1][1] = dp[0][0] + dp[1][0] = 1
   dp[1][2] = dp[0][1] + dp[1][1] = 2
   dp[1][3] = dp[0][1] + dp[1][2] = 3
   dp[1][4] = dp[0][2] + dp[1][3] = 4
   .
   .
   .
   dp[2][1] = dp[1][0] + dp[2][0] = 0
   dp[2][2] = dp[1][1] + dp[2][1] = 1
   dp[2][3] = dp[1][1] + dp[2][2] = 2
   dp[2][4] = dp[1][2] + dp[2][3] = 4
   .
   .
   .
   
   

2번째코드는 WOOSERK님의 문제풀이를 보고 이해했습니다. 

소스코드

첫번째 코드

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

import static java.lang.System.in;

public class 로또 {
    private static int N;
    private static int M;
    private static long answer;
    private static long[][] dp;
    private static ArrayList<Integer> arrayList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        int T = Integer.parseInt(br.readLine());
        String[] strArr;
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            arrayList = new ArrayList<>();
            answer = 0;
            strArr = br.readLine().split(" ");
            N = Integer.parseInt(strArr[0]);
            M = Integer.parseInt(strArr[1]);
            dp = new long[N][M + 1];

            // 범위
            int m = M;
            arrayList.add(M);
            for (int i = 0; i < N - 1; i++) {
                m /= 2;
                arrayList.add(m);
            }


            // 정답 도출
            for (int i = 1; i <= arrayList.get(N - 1); i++) {
                answer += get(i, N - 1);
            }
            sb.append(answer + "\n");
        }
        System.out.println(sb);
    }

    private static long get(int num, int restCount) {
        if (restCount == 0) {
            return 1;
        }

        int next = num * 2;
        long sum = 0;
        for (int i = next; i <= arrayList.get(restCount - 1); i++) {
            if (dp[restCount][i] == 0) {
                dp[restCount][i] = get(i, restCount - 1);
            } else{
            }
            sum += dp[restCount][i];
        }

        return sum;
    }

}

 

두번째 코드

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

public class 로또 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // dp 알고리즘
        long[][] dp = new long[11][2001];
        for (int i = 0; i <= 2000; i++) { // 초기화
            dp[0][i] = 1;
        }

        for (int i = 1; i <= 10 ; i++) { // 자릿수
            for (int j = 1; j <= 2000 ; j++) { // 값
                dp[i][j] = dp[i - 1][j / 2] + dp[i][j - 1];
            }
        }

        // 정달 출력
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        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.println(sb);
    }
}