[DFS] 5. 동전교환

<<풀이>>

-나의 풀이-

이 문제는 DFS로 쉽게 풀 수 있다. 동전 종류의 갯수만큼 계속해서 더해서 그 값이 최종 타겟 값이 되면 그 때 값을 최솟값 비교로 답을 도출해낸다. 만약 그 값이 타겟 값을 넘어서버리면 return 하게끔 했다.

 

결국 정답은 맞췄다. 

하지만,  시간 초과가 떴다 ,, 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    static int answer;
    int min = Integer.MAX_VALUE;
    private void DFS(int L, int T, int n, int z, int[] arr) {
        if (T > z) return;
        if (T == z) {
            min = Math.min(min, L);
            return;
        } else {
            for (int i = 0; i < n; i++) {
                DFS(L + 1, T + arr[i], n, z, arr);
            }
        }
        answer = min;
    }


    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String m = br.readLine();
        int[] arr = new int[n]; // 여기서 new int[n]을 안 써도 밑 stream을 통해 자동으로 만들어 준다.
        arr = Arrays.asList(m.split(" "))
                .stream().mapToInt(Integer::parseInt).toArray();
        int z = Integer.parseInt(br.readLine());

        T.DFS(0, 0, n, z, arr);
        System.out.print(answer);

    }
}

 

그래서 트리는 왼쪽에서 오른쪽으로 탐색하는 형태이므로, 가장 큰 동전으로 먼저 계산해주기 위해서 정렬을 한 뒤 가장 큰 값부터 먼저 계산 되도록 고쳤다. 하지만 이것도 시간 초과 ㅠㅠ 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

class Main {
    static int answer;
    int min = Integer.MAX_VALUE;
    private void DFS(int L, int T, int n, int z, int[] arr) {
        if (T > z) return;
        if (T == z) {
            min = Math.min(min, L);
            return;
        } else {
            for (int i = n - 1; i >= 0; i--) {
                DFS(L + 1, T + arr[i], n, z, arr);
            }
        }
        answer = min;
    }


    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String m = br.readLine();

        int[] arr = Arrays.asList(m.split(" "))
                .stream().mapToInt(Integer::parseInt).toArray();

        Arrays.sort(arr);

        int z = Integer.parseInt(br.readLine());

        T.DFS(0, 0, n, z, arr);
        System.out.print(answer);

    }
}

 

도대체 어떻게 풀어야 할까?? 강사님의 수업을 들어보자,,

 

-강사님 풀이-

 

ㅋㅋㅋㅋㅋ 정말 간단한 문제 였다. 생각해보면 우리가 구하고자 하는 최솟값보다 더 큰값이라면. 굳이 더 더해서 답을 도출할 필요가 없다. 어차피 최솟값은 그대로 유지가 되기 때문이다. 그래서 조건을 하나 더 달면 바로 시간 초과라는 문제를 해결할 수 있었다 ㅋㅋ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

class Main {

    static int answer = Integer.MAX_VALUE;
    private void DFS(int L, int T, int n, int z, Integer[] arr) {
        if (T > z || L > answer) return;
        if (T == z) {
            answer = Math.min(answer, L);
            return;
        } else {
            for (int i = 0; i < n; i++) {
                DFS(L + 1, T + arr[i], n, z, arr);
            }
        }
    }


    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String m = br.readLine();

        Integer[] arr = Arrays.asList(m.split(" "))
                .stream().map(Integer::valueOf)
                .toArray(Integer[]::new);

        Arrays.sort(arr, Collections.reverseOrder());

        int z = Integer.parseInt(br.readLine());

        T.DFS(0, 0, n, z, arr);
        System.out.print(answer);

    }
}

 

이 밑의 풀이는 강사님이 힌트 주자 마자 바로 적용해서 정답을 맞춘 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

class Main {

    static int answer = Integer.MAX_VALUE;
    private void DFS(int L, int T, int n, int z, int[] arr) {
        if (T > z || L > answer) return; // 바로 이부분 !!
        if (T == z) {
            answer = Math.min(answer, L);
            return;
        } else {
            for (int i = n - 1; i >= 0; i--) {
                DFS(L + 1, T + arr[i], n, z, arr);
            }
        }
    }


    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String m = br.readLine();

        int[] arr = Arrays.asList(m.split(" "))
                .stream().mapToInt(Integer::parseInt).toArray();

        Arrays.sort(arr);

        int z = Integer.parseInt(br.readLine());

        T.DFS(0, 0, n, z, arr);
        System.out.print(answer);

    }
}

 

        if (T > z || L > answer) return;

 

비록 어이는 없었지만 이 작은 것 하나로 인해 계산 속도에 큰 차이를 줄 수 있다는 교훈을 얻고 간다.

 

<<추가 공부>>

Arrays.sort(arr, Collections.reverseOrder());

 

 일반적으로 오름차순을 진행할 때에는 Arrays.sort(배열) 로 바로 구할 수 있지만, 내림차순인 경우는 for문을 돌릴때 반대로 해주거나

위의 방식대로 Collections의 내장 클래스를 활용해야 한다. 이때 arr배열의 데이터는 객체로 되어야 하므로 int가 아닌, wrapper 클래스로 바꿔준 Integer 타입으로 들어가야 한다! 

 

그래서

Integer[] arr = Arrays.asList(m.split(" "))
        .stream().map(Integer::valueOf)
        .toArray(Integer[]::new);

 

이렇게 변형을 시켜준다.