글 읽기 - 시간초과 질문드립니다.

wow1514 8년 전 0

아래와 같이 재귀로 구현했는데

시간초과가 뜹니다.

이문제 dp문제인가요?

import java.util.Scanner;

public class hotel{
	static int N,C;
	static int[] cost,effect;
	static int min;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		C = sc.nextInt();
		N = sc.nextInt();
		cost = new int[N];
		effect = new int[N];
		min = 10000;
		for(int i = 0; i < N; i++){
			cost[i] = sc.nextInt();
			effect[i] = sc.nextInt();
		}
		process(0,0);
		System.out.println(min);
		sc.close();
	}
	static void process(int ctotal, int total){
		if(total > C)
			return;

		if(total == C){
			if(ctotal < min)
				min = ctotal;
			return;
		}
		else
			for(int i = 0; i < N; i++){
				process(ctotal+cost[i],total+effect[i]);
			}

	}
}

chatterboy 8년 전 0

네. dp로 해결 가능 하네요.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

wow1514 8년 전 0

chatterboy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말