글 읽기 - 동전 조합찾기 탐색문제 시간초과 질문입니다.

kdh9520 9년 전 0

아래코드와 같이 탐색해서 찾았는데 시간초과가 나오네요.

중간에 호출직후 현재 최소값보다 커지면 가지치기 해주었고,

파라미터없이 전역변수로 다돌려서도 넣어봤지만 아래코드와 마찬가지로 시간초과네요..

로직자체가 잘못된 것인가요?

import java.util.*;
import java.io.*;

class Main {

	private static int num, target, nowMoney, min;
	private static int[] cArr;

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);

		num = keyboard.nextInt();
		target = keyboard.nextInt();

		cArr = new int[num];

		for (int i = 0; i < num; i++) {
			cArr[i] = keyboard.nextInt();
		}
		min = Integer.MAX_VALUE;
		nowMoney = target;
		compute(num - 1, 0);

		if (min == Integer.MAX_VALUE)
			min = -1;
		System.out.println(min);
	}

	private static void compute(int nowIndex, int nowCount) {
		if (nowCount >= min) {
			return;
		}
		if (nowMoney < 0)
			return;
		if (nowIndex < 0) {

			return;
		}

		if (nowMoney == 0) {
			if (min > nowCount) {
				min = nowCount;
				return;
			}
		}

		// 지금동전넣은것
		nowMoney -= cArr[nowIndex];
		compute(nowIndex, nowCount + 1);
		nowMoney += cArr[nowIndex];

		// 안쓴것
		compute(nowIndex - 1, nowCount);

	}

}

pichulia 9년 전 0

cash를 추가해서

불필요한 연산을 제거해보세요.

	private static int[] cash = new int[target+1];
    private static void compute(int nowIndex, int nowCount) {
		//blabla
		if(cash[nowMoney] < nowCount)
			return;
		cash[nowMoney] = nowCount;
        
        // 지금동전넣은것
        nowMoney -= cArr[nowIndex];
        compute(nowIndex, nowCount + 1);
        nowMoney += cArr[nowIndex];
 
        // 안쓴것
        compute(nowIndex - 1, nowCount);
 
    }

pichulia 9년 전 1

저거 추가한다고 해결되진 않네요...이런;ㅋㅋㅋ

화이팅(..?!!)

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB...

만능 링크 던지고 도망갑니다

kdh9520 9년 전 0

안되네요 ㅜㅜ 어떻게해야되지..

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

문제

문제

출처

ICPC

동전 조합찾기 탐색문제 시간초과 질문입니다.

kdh9520 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 1

kdh9520 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말