8-5 동전 교환

** 코드

 

package inflearn_8_dfs_bfs_uses;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.StringTokenizer;
 
public class inflearn8_5 {
    static int n,m,k;
    static Integer[]arr;
    static int total;
    static StringTokenizer st;
    static StringBuilder sb;
    static Set<Integer> set;
    static boolean[] visited;
    static int min;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        arr = new Integer[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        m = Integer.parseInt(br.readLine());
        Arrays.sort(arr, Collections.reverseOrder());
        min = Integer.MAX_VALUE;
        dfs(0,m,0);
        System.out.println(min);
        br.close();
        bw.close();
    }
    static void dfs(int index, int sum, int cnt) {
        if(index>=n) {
            if(sum==0) {
                min = Math.min(min, cnt);
            }
            return;
        }
        dfs(index+1, sum%arr[index], cnt+(sum/arr[index]));
        dfs(index+1, sum, cnt);
    }
}
 

 

그리적으로 풀려고 했는데 실패했다. 그리디로 해서 시간초과가 떴는데 DFS로 풀어서 시간초과가 안뜨는게 왜인지 모르겠다.

DFS의 파라미터로 index, 남은 거스름돈, 사용한 동전의 개수를 전달하며 min에다 최소값을 넣는 방식으로 풀었다.

package inflearn_8_dfs_bfs_uses;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.StringTokenizer;
 
public class inflearn8_5 {
    static int n,m,k;
    static int[]arr;
    static int total;
    static StringTokenizer st;
    static StringBuilder sb;
    static Set<Integer> set;
    static boolean[] visited;
    static long max;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        Integer[] arr = new Integer[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        m = Integer.parseInt(br.readLine());
        Arrays.sort(arr, Collections.reverseOrder());
        int index=0;
        int cnt=0;
        while(m>0) {
            if(m/arr[index]>0) {
                cnt+=m/arr[index];
                m = m%arr[index];
            }
        }
        System.out.println(cnt);
        br.close();
        bw.close();
    }
}
 

 

하지만 그리디적으로 푼다면 훨씬 간단하고 빠르게 풀릴 것 같았는데 이유를 찾아야한다.

+ index++ 즉, 인덱스값에 대한 증가를 안써서 안됐던 것이었다.

++ 테스트케이스의 값을 보니 최대값으로 나누는 그리디적인 사고방식으로는 정답값이 안나오는 케이스가 존재했다.

즉, 가장 높은 값을 순차적으로 빼면서 값을 더해나가는 방식이 아니라

모든 과정을 한번씩 돌아보며 최적의 값을 더해내는 DFS 로직이 아니면 정답값이 나올 수 없었다.