글 읽기 - 2294번 자바 시간초과 질문드립니다.

woalskdl 2년 전 0

안녕하세요.

dp 함수를 이용하여 풀이하는 방식으로 풀어봤는데요. (코드의 상단이 제 풀이, 하단이 검색을 통해 얻은 풀이입니다)

시간초과가 발생해서 여러가지 시도들 (Hashset 이용 동전 중복 제거, 배열 정렬 - 큰수부터 탐색 등)을 해봤는데 여전히 시간초과가 되더라구요.

검색해서 풀이를 해보니, 점화식을 이용하여 이중 for문을 사용하여 풀이를 하던데,

사실 제 방식과 어떤 부분에서 달라 더 시간이 빠르게 적용되는지 이해가 되지 않아 질문드립니다.

결국 이중 for 문을 돌면서 배열을 전부 체크하는 방식이 적용된것 같은데, 제가 보기엔 오히려 더 비효율적인게 아닌가 싶은 생각이 드는데요..

어떤 부분에서 더 효율적으로 계산하게 되는것일까요?

고수님들 답변주시면 감사드리겠습니다!

좋은 하루 되세요 :)

// 제 풀이 --------------------------------

public class Main {

    private static int n;
    private static int k;
    private static int[] coins;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        coins = new int[n];
        arr = new int[k + 1];

        for(int i=0; i<=k; i++)
            arr[i] = -1;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int val = Integer.parseInt(st.nextToken());
            coins[i] = val;
            
            if(val <= k)
                arr[val] = 1;
        }

        System.out.println(dp(k));
    }

    private static int dp(int val){
        if(arr[val] != -1)
            return arr[val];

        int minVal = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
            if(coins[i] >= val)
                continue;
            
            int count = dp(val - coins[i]) + 1;
            if(count != 0 && minVal > count)
                minVal = count;
        }

        if(minVal == Integer.MAX_VALUE)
            minVal = -1;

        return arr[val] = minVal;
    }
}

// 인터넷 검색하여 얻은 풀이 ---------------------------------

public class P2994_answer {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coins = new int[n];

        for (int i = 0; i < n; i++)
            coins[i] = Integer.parseInt(br.readLine());

        int[] dp = new int[k + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        if(dp[k] == Integer.MAX_VALUE - 1)
            System.out.println(-1);
        else
            System.out.println(dp[k]);
    }
}

djm03178 2년 전 1

우선, 코드는 항상 제출했던 코드 전체를 그대로 올려주세요. 이 코드는 import가 없어서 직접 테스트해보려면 번거롭게 하나 하나 다 추가해야 됩니다.

문제가 되는 부분은 49~50번째 줄입니다. top-down dp에서 중요한 것은 각 상태에 대한 답은 한 번만 구해야 한다는 점인데, 되는 경우를 찾지 못했다고 해서 다시 초기 상태로 되돌리면 이후에 이 상태를 다시 방문했을 때 답을 못 찾았다는 정보를 그대로 사용하는 것이 아니라 다시 처음부터 계산하게 되어 비효율적입니다. 이런 경우 그냥 적당히 답이 될 수 없는 큰 값을 반환하도록 해주면 됩니다.

-1을 출력하는 로직은 반환된 값이 그 적당히 큰 값인 경우에 해주면 됩니다.

woalskdl 2년 전 0

안녕하세요. 좋은 답변 감사드립니다!

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

문제

문제

출처

ICPC

2294번 자바 시간초과 질문드립니다.

woalskdl 2년 전 0

djm03178 2년 전 1

woalskdl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말