[DP] 백준 알고리즘 2758번 로또

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

Github : https://github.com/ddulhddul/algorithm

시간을 줄이는대로 줄여봤지만, 시간초과로 실패

조금더 생각해 봐야할 듯

소스코드

import java.io.File;
import java.io.FileNotFoundException;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Baekjoon2758 {
	
	public static void main(String[] args) throws FileNotFoundException {

		long start = System.currentTimeMillis();
		
		File file =new File("D:\\dev\\worksspace\\Solution\\src\\sample.txt");
		Scanner sc = new Scanner(file);
		
		int test_case_num = 0;
		int max_test_case = Integer.parseInt(sc.nextLine());
		
		while (sc.hasNext()) {
			if(test_case_num >= max_test_case) break;
			
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			test_case_num++;
			
			solutionMap = new HashMap();
			powMap = new HashMap();
			
			BigDecimal result = solveProb(n, m);
			
			
			System.out.println(result);
			//System.out.println(solutionMap.toString());
		}
		sc.close();

		long end = System.currentTimeMillis();
		System.out.println( "실행 시간 : " + ( end - start )/1000.0 );
	}

	private static BigDecimal solveProb(int n, int m) {
		BigDecimal result = BigDecimal.ZERO;
		
		for (int i = 1; i < m; i++) {
			Stack q = new Stack();
			q.add(i);
			result = result.add(fnSolution(i, n-1, m, q));
			if(result.compareTo(BigDecimal.ZERO) == 0) break;
		}
		
		return result;
	}
	
	static Map solutionMap = new HashMap();
	static Map powMap = new HashMap();
	
	private static BigDecimal fnSolution(int i, int n, int m, Stack q) {
		BigDecimal result = BigDecimal.ZERO;
		
		
		/* i : selected value 
		 * n : remain count
		 * m 
		 * */
		
		if(i*Math.pow(2, n) <= m){
			//다 선택했으면
			if(n == 0){
				result = result.add(BigDecimal.ONE);
				//테스트케이스를 보기위한 sysout
				//System.out.println(q.toString());
			}else{
				for (int j = i*2; j <= m; j++) {
					//q.add(j);
					
					BigDecimal solutionInt = solutionMap.get(j+"/"+(n-1));
					if(solutionInt == null){
						result = result.add(fnSolution(j, n-1, m, q));
					}else{
						result = result.add(solutionInt);
					}
					
					//q.remove(q.size()-1);
				}
				solutionMap.put(i+"/"+n, result);
			}
		}
		
		return result;
	}


}