🔗 Problem

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

👩‍💻 Code - Dynamic Programming

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

// 로또

public class BJ2758 {
	
	static int t;
	static int n;
	static int m;
	static long[][] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			dp = new long[n+1][m+1];
			
			solution();
			
		}
	}
	
	private static void solution() {
		
		for(int i = 1; i <= m; i++) {
			dp[1][i] = 1;
		}
		
		for(int i = 2; i <= n; i++) {
			for(int j = 2; j <= m; j++) {
				
				if(j%2 == 0) {
					dp[i][j] = dp[i][j-1] + dp[i-1][j/2];
				}
				else {
					dp[i][j] = dp[i][j-1];
				}
			}
		}
		
		long cnt = 0;
		int start = (int)Math.pow(2, n-1);		// n번째 고르는 수 중 가장 작은 값
		for(int i = start; i <= m; i++) {
			cnt += dp[n][i];
		}
		
		System.out.println(cnt);
	}
	
	
}

👩‍💻 Code - Back Tracking

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

// 로또
/* Back Tracking으로 구현하면 백준에서는 시간 초과 발생
DP로 해결하였음 */

public class BJ2758_2 {
	
	static int t;
	static int n;
	static int m;
	static int cnt;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			cnt = 0;
			backTracking(0, 0);
			
			System.out.println(cnt);
		}
	}
	
	private static void backTracking(int depth, int idx) {
		
		if(depth == n) {
			cnt++;
			return;
		}
		
		if(idx * 2 <= m) {		// isPromising() 조건
			for(int i = idx*2; i <= m; i++) {
				if(depth == 0 && i == 0) continue;
				backTracking(depth + 1, i);
			}
		}
		else return;
		
		
	}
}

💡 Learned

아이디어

• 처음에 Back Tracking으로 구현해서 시간 초과 발생함.
• n by m matrix 만들고 n번째 자리에 m이 놓일 수 있는 경우의 수를 담았다.

틀렸습니다

• dp[][]와 cnt를 실수형 double로 선언해서 틀렸다.
• 출력이 몇 개인지 묻는 것이므로 정수형 long으로 변경하여 해결함.