구름톤 챌린지 2주 Day3 - 통증

통증 (Java)

 

제출한 답 :

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 플레이어의 통증 수치

        int[] items = {14, 7, 1}; // 아이템의 감소 수치 (크기별로 내림차순 정렬된 상태)

        int itemIndex = 0; // 아이템 인덱스
        int itemCount = 0; // 아이템 개수

        while (n > 0) {
            if (n >= items[itemIndex]) {
                n -= items[itemIndex];
                itemCount++;
            } else {
                itemIndex++;
            }
        }

        System.out.println(itemCount);
    }
}

이번엔 좀 쉽다?? 별 두개의 난이도가 이렇게 달라서야;;;  난이도가 좀 이상한거 같기도 하고?

그리디 문제를 여러번 풀어서 익혀두면 좋을 것 같다.

 

Greedy에 대해서 알아보자!

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

 

문제 풀이

필요한 개념

• 그리디 알고리즘

분석

이 문제는 통증을 가장 많이 줄여주는 아이템을 선택하여 통증을 최소화하는 것이 목표입니다. 통증을 줄이는 아이템들의 개수를 합하여 출력하면 됩니다.

문제 풀이

그리디 알고리즘을 사용하여 통증을 가장 많이 줄여주는 순서대로 아이템을 선택합니다. 선택한 아이템의 개수를 누적하여 최종적으로 출력하면 됩니다.

하지만, 풀이가 단순한만큼 왜 이러한 그리디 알고리즘을 적용해서 문제를 해결할 수 있는지 아는 것이 중요합니다.

그리디와 그리디가 아닌

그리디 알고리즘은 보통 탐욕법이라고 번역을 하곤 합니다. 말 그대로 문제를 해결할 때 있어서 현재 경우만 고려해서 최적의 상황을 선택하는 방법입니다.

당연하게도 이런 선택이 항상 최적해를 구할 수 있는 방법은 아니기 때문에, 항상 사용할 수 있는 방법은 아닙니다. 하지만 다음 두 가지 조건이 성립한다면 그리디 알고리즘을 기계적으로 적용할 수 있다고 알려져 있습니다.

• 현재의 최적의 선택이 다음 선택에 영향을 미치지 않는다.
• 현재의 선택이 최종 선택의 최적 해결 방법에 포함된다.

이 내용만 얼핏 봐선 언제 그리디 알고리즘을 적용할 수 있는지 알기 어렵습니다. 실제로 어떤 문제에 대한 사전 지식이 없이, 그 문제를 그리디로 해결할 수 있을지 증명하는 것은 어렵습니다.

하지만 일반적인 코딩 테스트 정도의 레벨에서 나오는 유형은 한정되어 있습니다. 따라서 자주 나오는 몇 가지 상황에 대해 그리디로 해결할 수 있음을 알고 있으면, 이를 응용하는 문제를 만났을 때 훨씬 편하게 대처할 수 있을 것입니다.

동전 교환 문제

이 문제는 동전 교환 문제로 잘 알려진 유형입니다. 사실 모든 동전 교환 문제가 그리디 알고리즘으로 해결되는 것은 아닌데, 이 문제와 같이 모든 값이 배수 관계에 있으면 그리디하게 문제를 해결할 수 있습니다.

이 사실을 바탕으로, 통증 문제를 보시면, bandage, medicine, painkiller 가 통증 수치를 줄여지는 값이 1 ,7 ,14로 서로 배수 관계임을 알 수 있습니다. 가령 20의 통증을 줄이기 위해서는 진통제 1개, 밴드 6개가 사용하는 것이 아이템의 최소 개수입니다.

가장 많이 통증을 줄여주는 것부터, 채워 나가는 것이 통증 문제를 해결하는 포인트입니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 입력값 N을 받아옴
        int N = scanner.nextInt();
        scanner.close();

        // 결과값을 저장할 변수 초기화
        int ans = 0;
        // 주어진 진통제 단위를 배열로 선언
        int[] painKiller = {14, 7, 1};
        // 배열을 순회하면서 지폐 단위로 나눠주고 나머지를 업데이트하여 최종 결과값 계산
        for (int i : painKiller) {
            ans += N / i;
            N %= i;
        }
        // 최종 결과값 출력
        System.out.println(ans);
    }
}