구름톤 챌린지 2주차 - 3번

8일차 - 통증

---

문제 내용

• 통증 수치 N이 주어집니다.
• 통증 수치를 줄이는 아이템 3개가 주어집니다. bandage, medicine, painkiller로 구성되며 각각 통증 수치를 1, 7, 14만큼 줄여줍니다
• 아이템을 사용할 때, 통증 수치가 0 아래로 떨어질 경우, 아이템을 사용할 수 없습니다.
  • ex) 통증 수치가 6일 경우, 통증 수치를 7 줄여주는 medicine을 사용하면 통증 수치가 -1이 되므로 사용 불가능, 그러나 통증 수치를 1 줄여주는 bandage는 사용가능.
• 통증 수치를 0으로 만드는 데 필요한 아이템의 최소 개수를 구하는 것이 목표.

해결 방법

• 그리디 알고리즘을 활용합니다.(순간순간 최적의 해를 구함)
• 최대한 통증 수치를 많이 줄여주는 아이템을 순간순간 선택하는 방식을 이용합니다.
• painkiller(-14) -> medicine(-7) -> bandage(-1) 순으로 아이템을 가능한 많이 소모하고, 소모할 수 없으면 다음 아이템을 사용하는 방식을 채택합니다.
  • ex) 통증 수치가 29일 경우 -> painkiller(-14)를 최대한 많이 사용 -> 29 - 14 2 = 1 -> medicine(-7)을 사용할 수 없음 -> bandage(-1)를 가능한 많이 사용 -> 1 - 1 1 = 0 -> 필요한 최소 아이템 수 = 3개
• 사용한 아이템 수는 나눗셈 결과로, 남은 통증 수치는 나머지를 통해 계산 가능.
  • 통증 수치가 29일 경우, painkiller(-14)를 사용할 때 사용할 수 있는 아이템 수는 29 / 14 = 2개(int), 남은 통증 수치는 29 % 14 = 1.

주의 사항

• 남은 통증 수치를 계산할 때, 결과는 정수형으로 처리해야함에 유의합시다.

작성 코드

#include <iostream>
using namespace std;
int main() {
	int sum = 0; // 사용한 아이템의 최소 개수
	int n; // 통증 수치
	cin >> n;
    /*그리디 알고리즘을 통한 아이템 개수 계산*/
	if(n >= 14) {
		sum += n / 14; // 사용한 아이템 수 추가
		n %= 14; // 남은 통증 수치 계산
	}
	if(n  >= 7) {
		sum += n / 7;
		n %= 7;
	}
	if(n >= 1)
		sum += n;
	cout << sum << endl;
}

소감

• 처음으로 나온 그리디 알고리즘 문제였기에 어렵진 않은 문제였습니다.
• 그리디 알고리즘의 개념의 기초를 다질 수 있는 좋은 문제였습니다.