글 읽기 - dp로 푸는데도 시간초과가 나오네요

(追記) (追記ここまで)

dp로 푸는데도 시간초과가 나오네요

9084번 - 동전

jihea37 9년 전 0

여기서 더 어떻게 줄여야하는지 모르겠습니다.

시간초과가 납니다.

import java.util.Scanner;
import java.util.Vector;
class Main {
	
	static int[][] D = new int[10001][20];
	static int[] coin;
	static int m;
	static int sum=0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t= sc.nextInt();	//testcase
		
		for(int tt=0; tt<t; tt++){
		int n = sc.nextInt();
		coin = new int[n];
		sum=0;
		
		for(int i=0; i<n; i++){
			coin[i]=sc.nextInt();
		}
		
		m = sc.nextInt();
		for(int i=0; i<10001; i++){
			for(int j=0; j<n; j++){
				D[i][j]=0;
			}
		}
		
		System.out.println(dp(0,0));
		}
	}
	
	public static int dp(int money, int index){
		
//		System.out.println(money+" **");
		
		if(money==m){
			return 1;
		}
		if(money>m){
			return 0;
		}
		
		if(D[money][index]!=0){
			return D[money][index];
		}
		
		for(int i=index; i<coin.length; i++){
			D[money][index]+=dp(money+coin[i], i);
		}
		return D[money][index];
		
	}
}

zlzmsrhak 9년 전 0

입력 조건과 맞지 않아 완벽한 반례는 아니지만, 이런 데이터도 시간 내에는 나와야 합니다.

D 배열의 초기값을 0으로 정할 경우, 실제 계산값이 0일 때 계산한 값임에도 불구하고 47~49번째 줄을 건너뛰어 시간이 오래 걸릴 수 있습니다.

1
10
100 101 102 103 104 105 106 107 108 109 
10000

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC