글 읽기 - 자바) DP, 비트마스크 다 썼느데 왜 시간초과가 날까요..?ㅠㅠ

mhi0118 4년 전 1

dp에 비트마스크도 쓰고 각 숫자별로 나머지를 바로 구할 수 있도록 theRest[rest][n] 도 만들었는데 왜 시간초과가 뜰까요?ㅠㅠㅠ 도와주세요

	import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
	
	public class Main {
		
		static int n, k;
		static long[][] dp;
		static int[][] theRest;
		static char[][] c;
		public static void main(String args[]) throws IOException {
		
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
			n = Integer.parseInt(br.readLine());

			c = new char[n][];
			for(int i=0; i<n; i++) c[i] = br.readLine().toCharArray();
			
			k = Integer.parseInt(br.readLine());
			
			theRest = new int[k][n];
			dp = new long[k][1<<n];
			
			for(int i=0; i<k; i++) {
				Arrays.fill(theRest[i], -1);
				Arrays.fill(dp[i], -1);
			}
			
			long num = makeAnswer(0, 0);
			
			
			
			if(num==0) System.out.print(0+"/"+1);
			else {
				long count = n-1;
				long m = n;
				while(count!=1) {
					m *= count;
					count--;
				}
				long divide = 2;
				while(divide<=num) {
					if(num%divide==0&&m%divide==0) {
						num /= divide;
						m /= divide;
						continue;
					}
					else divide++;
				}
				System.out.print(num +"/"+ m);
			}
			
		}
		
		static long makeAnswer(int rest, int visit) {
			if(visit==((1<<n)-1)) {
				if(rest==0) return 1;
				else return 0;
			}
			
			if(dp[rest][visit]!=-1)
				return dp[rest][visit];
			
			dp[rest][visit] = 0;
			
			for(int i=0; i<n; i++)
				if(((1<<i)&visit)==0) {
					if(theRest[rest][i]==-1) {
						int nextNum = rest;
						for(int a=0; a<c[i].length; a++)
							nextNum = (nextNum*10 + c[i][a]-48)%k;
						
						theRest[rest][i] = nextNum;
					}
					dp[rest][visit] += makeAnswer(theRest[rest][i], (1<<i)|visit);
				}
			
			return dp[rest][visit];
		}
			
	}

mhi0118 4년 전 0

문제에서 주어지는 최대의 입력을 집어넣어도 바로 답이 나오는데 왜그럴까요..ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바) DP, 비트마스크 다 썼느데 왜 시간초과가 날까요..?ㅠㅠ

mhi0118 4년 전 1

mhi0118 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말