[백준] 11047 - 동전 0

백준 바로가기

11047번: 동전 0

거스름돈 최소 동전 개수로 구하는 문제를 이전에 풀어봤기 때문에 어렵진 않았다. 하지만 혼자 틀린 반례를 상상하느라 이상한 조건을 넣어줘 한 번 틀렸다. 주어지는 동전 가치는 i번째 동전이 i-1번째 동전의 배수이기 때문에 만일 target 동전 값이 700일 때 500과 300이 동시에 존재할 수는 없다. 만일 300이 있다면 500보다 300을 넣고 나머지를 1로 채워줘야 한다. 

음 사실 정확하게 왜 추가 조건이 필요없는지 이해는 못하겠지만 구구단이랑 비슷하다고 생각된다. 모두 배수일 땐 큰 수로 최대한 나누고 그 다음 큰 수로 나누면서 나머지를 줄여나가는 방법이 무조건 효율적이다. 만약 배수가 아닐땐? 그리디 알고리즘이 아닌 DP나 DFS 등 다른 알고리즘을 사용해야될 것 같다. 

1시간 써서 다 푼 문제. 실버 1 이상은 한 문제당 최소 1시간은 걸리는 구나... 흑

1) 데이터 '틀'

 

2) 문제해결 로직

본문과 정답코드로 갈음

3) 정답 코드

public class Coin0_11047 {
 
    static int[] coins;
    static int target;
    static int targetTemp;
    static int num;
    static int coinCnt;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        num = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
        targetTemp = target;
        coins = new int[num - 1];
        coinCnt = 0;
 
        //A1 == 1
        br.readLine();
 
        //동전 종류 coins에 저장
        for (int i = 0; i < num - 1; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
 
        //coins 오름차순 정렬
        Arrays.sort(coins);
 
        //문제 해결 반복문
        for (int i = num - 2; i >= 0; i--) {
            if (coins[i] > targetTemp)
                continue;
 
                coinCnt += targetTemp / coins[i];
                targetTemp %= coins[i];
        }
 
        //1보다 큰 가장 작은 동전으로 안나눠질 경우
        if (targetTemp > 0)
            coinCnt += targetTemp;
 
        System.out.println(coinCnt);
 
 
    }
}