글 읽기 - DFS로 풀어봤는데 런타임에러가 나네요..

cakimmy24 7년 전 0

임의로 숫자선택하고 논리대로 따라가보면서 글로 풀어봤는데도 에러날부분을 못찾겠네요 ㅠ 도와주세요

import java.util.LinkedList;
import java.util.Scanner;

public class Min_Coin {

	public static void push(LinkedList<Integer> q, int num){
		q.offer(num);
	}
	
	public static int pop(LinkedList<Integer> q){
		return q.poll();
	}
	
	public static boolean empty(LinkedList<Integer> q){
		if(q.isEmpty()) return true;
		else return false;
	}
	
	public static void BFS(int num, int prc[], int N, int K){
		
		LinkedList<Integer> q = new LinkedList<Integer>();
		
		int visit[] = new int[K+1];
		for(int i = 0; i < visit.length; i ++){
			visit[i] = -1;
		}
		
		push(q, K);
		visit[K] = 0;
		
		while(!empty(q)){
			
			int cur = pop(q);
			
			if(cur == 0){
				System.out.println(visit[cur]);
				return;
			}
			
			for(int i = num; i >= 0; i --){
				if((cur-prc[i]) >= 0){
					push(q, cur-prc[i]);
					visit[cur-prc[i]] = visit[cur] + 1;
					break;
				}
			}
            
		}	
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int K = in.nextInt();
		int prc[] = new int[N];
		
		for(int i = 0; i < N; i ++){
			prc[i] = in.nextInt();
		}
		
		int temp = 0;
		
		for(int i = 0; i < N; i ++){
			if(prc[i] > K){
				temp = i-1;
				break;
			}
			if(i == N-1 && prc[i] < K) {
				temp = i;
			}
		}
		
		BFS(temp, prc, N, K);
	
	}
}

zlzmsrhak 7년 전 1

K의 크기가 1억 정도이기 때문에, 23번째 줄에서 배열을 잡는 과정에서 문제가 생길 수 있습니다.

cakimmy24 7년 전 0

감사합니다 다시해보겠습니다 ^^

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

문제

문제

출처

ICPC

DFS로 풀어봤는데 런타임에러가 나네요..

cakimmy24 7년 전 0

zlzmsrhak 7년 전 1

cakimmy24 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말