백준 11047번 동전 0 - 그리디 - 자바

문제는 다음과 같다.

동전 0 문제는 그리디 문제에 속한다.

그리디에 대한 설명은 타 블로그의 포스트를 참조하였으니 궁긍하면 하단을 참고해주시면 될 것 같다!

 

누군가에게는 쉬울 수 있는 문제이지만 나는 꽤 오랜 시간이 걸렸던 문제이다.

 

내가 포인트로 배운 부분은 다음과 같다.

1. 입력 시 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어지는 값을 넣는 방법

2. 동전 개수의 최솟값을 구하기 위해서 i--로 로직을 구하는 방법

3. 첫 코드가 틀린 이유와 수정된 방향

 

1. 입력 시 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어지는 값을 넣는 방법

// 둘째 줄부터 N개의 줄에 동전의 값 Ai 입력 받기
        int[] coins =new int[N];
        for (int i = 0; i < N ; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

 

값을 받는 방법은 비교적 쉽다. coins라는 배열에 br.readLine을 하나씩 넣었다.

 

2. 동전 개수의 최솟값을 구하기 위해서 i--로 로직을 구하는 방법

<로직 구하기 전>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        // 첫째 줄에서 N과 K 입력 받기
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        // 동전 개수의 최솟값
        int minCount;

        // 둘째 줄부터 N개의 줄에 동전의 값 Ai 입력 받기
        int[] coins =new int[N];
        for (int i = 0; i < N ; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        
        // 로직 구현하기
        for (int i = coins.length; i>0; i--) {
            coins[i]

        }

 

 

 

고안한 로직방법은 for문을 활용하여 K에게 해당하는 큰 값을 배열에서 확인하고 뽑아서 빼는 방법을 택했다.

이 때, 로직을 수행할 때마다 동전의 갯수는 +=하는 방법으로 고안했다.

 

그렇게 구현한 코드는 아래와 같다.

   // 동전 갯수 최솟값 구하는 로직
        for (int i = coins.length -1 ; i>0; i--) {
            
            // 배열 중 K에 속하는 최대 값을 점점 빼주면서 동전 갯수 올리기
            while (K >= coins[i]) {
                K-= coins[i];
                minCount ++;
            }
        }

 

그런데 틀렸다는 답변이 나왔다.

실수가 벌어진 것이다.

 

3. 첫 코드가 틀린 이유와 수정된 방향

문제는 2가지 였다.

첫째, 배열에서 0번째 배열을 생각하지 않은 것

for (int i = coins.length -1 ; i>0; i--) {

i >= 0으로 수정하였다!

 

둘째, While의 무한루프를 고려하지 않았다.

coins[i]가 0일 때, K가 0보다 크거나 같은 동안 계속해서 루프에 진입할 수 있다. 그러면 K를 계속해서 0으로 만들어 무한 루프에 빠질 가능성이 있기 때문에 오류가 발생한 것이다.

그래서 코드를 while (coins[i] > 0 && K >= coins[i]) {로 수정하였다!

 

완성코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        // 첫째 줄에서 N과 K 입력 받기
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        // 동전 개수의 최솟값
        int minCount = 0;

        // 둘째 줄부터 N개의 줄에 동전의 값 Ai 입력 받기
        int[] coins =new int[N];
        for (int i = 0; i < N ; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        // 동전 갯수 최솟값 구하는 로직
        for (int i = coins.length -1 ; i >= 0; i--) {
        
            // 배열 중 K에 속하는 최대 값을 점점 빼주면서 동전 갯수 올리기 - 선택절차, 적절성 검사
            while (coins[i] > 0 && K >= coins[i]) {
                K-= coins[i];
                minCount ++;
            }
        }
        System.out.println(minCount); // - 해답 검사
    }
}

 

 

11047번: 동전 0

 

그리디 설명

💡 그리디 알고리즘 적용

- 해당 문제에서 그리디 알고리즘을 적용한다면 아래와 같습니다.

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택을 합니다.
2. 적절성 검사: 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택합니다.
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결되었습니다.

출처: https://adjh54.tistory.com/212 [Contributor9:티스토리]

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

 

그리디 문제라고 말하였지만 제대로 된 적절성 검사를 하진 않은 것 같다.

완벽한 코드는 아니므로 참고만 해주시길 바라며 조언은 언제든 환영입니다!

 

오늘 배운 점

1. While의 무한루프를 주의하며 While문을 자주 연습하고 익히자.

2. 그리디의 기본 설명