[ 백준 / BOJ 2758 ] 로또 ( JAVA / 자바 )

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

2758번: 로또

 

문제

---

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다.

이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 수를 고를 때 각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고르기 때문이다.

예를 들어, n=4, m=10일 때, 선영이는 다음과 같이 고를 수 있다.

• 1 2 4 8
• 1 2 4 9
• 1 2 4 10
• 1 2 5 10

따라서 선영이는 로또를 4개 산다. 

선영이는 돈이 엄청나게 많기 때문에, 수를 고르는 방법의 수 만큼 로또를 구매하며, 같은 방법으로 2장이상 구매하지 않는다.

n과 m이 주어졌을 때, 선영이가 구매하는 로또의 개수를 출력하는 프로그램을 작성하시오

입력

---

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n과 m으로 이루어져 있다.

 

출력

---

각 테스트 케이스에 대해 선영이가 로또를 몇 개나 구매하는지 한 줄에 하나씩 출력한다.

 

풀이

---

DFS 로 풀어보려했으나 ㅡㅡ;; 메모리 초과가 발생...🥶

DP 로 해결해야하는 문제인듯........

1 2 6 과 1 3 6 와 같이 그 뒤에 일치하는 경우들이 많기 때문에 memorization 해주어야하는듯..

으아~

 

코드

---

1️⃣ DFS로 풀어보려했으나 ... 메!모!리! 초!과!

 // DFS 로 풀이 시 메모리 초과 발생 
    static boolean[] isVisted;
    static int n,m;
    static long answer;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        while(T-- > 0){
            String[] nm = br.readLine().split(" ");
            n = Integer.parseInt(nm[0]);
            m = Integer.parseInt(nm[1]);
            answer = 0;

            isVisted = new boolean[m+1];
            for(int i = 1; i <= m; i++){
                isVisted[i] = true;
                DFS(i, 1, String.valueOf(i));
                isVisted[i] = false;
            }

            System.out.println(answer);
        }      
    }
    private static void DFS(int now, int cnt, String str) {

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

        if(cnt > n)
            return;

        for(int i = now*2; i <= m ; i++){
            if(!isVisted[i]){
                isVisted[i] = true;
                DFS(i*2, cnt+1, str+i);
                isVisted[i] = false;
            }
        }
    }

2️⃣ DP로 해결‼️

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_BOJ_2758_로또 {

    // dp와 memorization 으로 해결해주어야함
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        while(testCase-- > 0){
            int N, M;
            StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
            
            N = Integer.parseInt(stringTokenizer.nextToken());
            M = Integer.parseInt(stringTokenizer.nextToken());

            long[][] dp = new long[N+1][M+1];

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

            for(int n = 1; n < N+1 ; n++){
                for(int m = 1; m < M+1 ; m++){
                    // n번째 숫자로 m을 선택하는 경우 + 선택하지 않는 경우
                    dp[n][m] = dp[n-1][m/2] + dp[n][m-1];
                }
            }

            System.out.println(dp[N][M]);
        }
    }
}