[java] 구름톤 8일차. 통증

문제

구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 0 으로 유지하는 것이 중요하다.
게임 안에는 통증 수치를 감소시켜 주는 아이템이 3 종류가 있다. 아이템의 이름은 bandage, medicine, painkiller 이고, 각 아이템을 사용 시 1, 7, 14 만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다.
플레이어는 적과의 전투에서 피해를 입어 현재 N의 통증 수치를 가지고 있다. 플리에어의 통증 수치를 0으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 0보다 작아지는 아이템은 사용할 수 없음에 유의하시오.

입력

첫째 줄에 플레이어의 통증 수치를 나타내는 정수 N이 주어진다.
- 1 <= N <= 10^9

출력

플레이어가 통증 수치를 0으로 줄이기 위해 필요한 아이템의 최소 개수를 출력한다.

---

import java.io.*;

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 count = 0;
        
        count += N / 14; // 14로 나눈 몫
        N %= 14; // 나머지
        
        count += N / 7; // 7로 나눈 몫
        N %= 7; // 나머지
        
        count += N; // 나머지 값에 대해 1씩 아이템 사용
        
        System.out.println(count);
    }
}

그리디 알고리즘을 이용하라는데 일단 그냥 마구잡이로 풀었다.

 

그리디 알고리즘(Greedy Algorithm)은 각 단계에서 가장 최적의 선택을 하는 방식으로 문제를 해결하는 알고리즘 설계 기법입니다. 그리디 알고리즘은 현재 상태에서 가장 좋아 보이는 선택을 계속해서 수행하여 전체적인 결과를 얻는 것을 목표로 합니다. 이 선택들이 모두 합쳐져서 전체적으로 최적의 해를 찾는 경우가 많습니다. 그리디 알고리즘은 최적해를 찾는 것보다 근사해(approximation)를 찾는 문제에 자주 활용됩니다.

그리디 알고리즘은 다음과 같은 특징을 가집니다:

1. 탐욕적 선택 속성 (Greedy-choice property): 각 단계에서 가장 최적의 선택을 하기 때문에 부분 문제들이 최적해로 이끌어집니다.
2. 최적 부분 구조 (Optimal substructure): 부분 문제의 최적해들이 전체 문제의 최적해로 이끄는 특성입니다.
3. 탐욕적 선택과 최적 부분 구조를 결합하면 전체 문제에 대한 최적해를 구할 수 있음을 보이는 것이 중요합니다.

그리디 알고리즘은 다양한 문제에 적용될 수 있습니다. 예를 들어, 거스름돈을 최소한의 동전으로 주는 문제, 활동 선택 문제(activity selection problem), 허프만 코딩 등이 그리디 알고리즘의 예시입니다.