글 읽기 - 왜 시간초과가 되나요?

ljo950924 4년 전 0

LinkedList를 배열 형태로 선언하고

i번째 숫자까지의 가능한 모든 경우를 저장합니다 (0<= <=20 범위 내)

문제에서 숫자의 개수가 3<=n<=100 라는 조건이 있는데

그럼 가능한 수식의 최대 가짓수가 2^(100-1) 개 이므로

이는 대략 1000*1000 이므로 이는 1초 안에 계산이 되지 않나요??

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

public class Main {
	static int n;
	static int[] arr;
	static LinkedList<Integer>[] dp;
	static int[] checked;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp = new LinkedList[n+1];
		checked = new int[n+1];
		for(int i=1; i<dp.length; i++) {
			dp[i] = new LinkedList<Integer>();
		}
		dp[1].add(arr[1]);
		checked[1] = 1;
		
		//n-1자리 까지의 조합
		LinkedList<Integer> ret = dp(n-1);
		
		int count=0;
		for(int i=0; i<ret.size(); i++) {
			if(ret.get(i) == arr[n]) count++;
		}
		System.out.println(count);
	
	}
	
	static LinkedList<Integer> dp(int n) {
		if(checked[n]!=0) return dp[n];
		
		LinkedList<Integer> prev = dp(n-1);
		for(int i=0; i<prev.size(); i++) {
			int tmp;
			
			tmp = prev.get(i)-arr[n];
			if(tmp>=0) {
				dp[n].add(tmp);
			}
			
			tmp = prev.get(i)+arr[n];
			if(tmp<=20) {
				dp[n].add(tmp);
			}
		}
		
		checked[n]=1;
		return dp[n];
	}
}

djm03178 4년 전 1

2^99는 633825300114114700748351602688 입니다. 1000 * 1000은 1000000입니다.

ljo950924 4년 전 0

아! 잘못 계산했네요;; 감사합니다

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

문제

문제

출처

ICPC

왜 시간초과가 되나요?

ljo950924 4년 전 0

djm03178 4년 전 1

ljo950924 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말