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

11일차 - 통증(2)

---

문제 내용

• 통증 수치 N이 주어집니다.(이전 구름톤 챌린지 2주차 3번 문제와 비슷합니다.)
• 통증 수치를 A,B만큼 줄여주는 아이템이 주어집니다. (A < B)
• 통증 수치를 0보다 작게 만들 수 없습니다.
  • ex) 통증 수치가 10일 경우, 통증 수치를 11 줄여주는 아이템은 사용할 수 없음.
• 이 때, 통증 수치를 0으로 만들기 위해 아이템을 최소한으로 사용하는 개수를 구합니다.(0으로 만들 수 없다면 -1을 출력)

해결 방법

• 통증 수치를 가장 많이 줄여주는 아이템, B로 통증 수치를 최소로 한 다음(sum에서 깎는 방식), 통증 수치를 작게 줄여주는 아이템으로 깎되, 깎을 수 없으면 사용한 B의 개수를 1개씩 깎으면서 A를 사용하는 방식을 반복합니다.
  • ex) 통증 수치가 28, B가 10, A가 9라면
  • B를 최대한 사용한다 -> 28 - 10 2 = 8 -> A를 사용할 수 없음, 통증수치 8 남음
    -> B를 하나 깎음. -> 8 + 10 = 18 -> B를 2개 사용, 18 - 9 2 = 0 -> 총 사용한 아이템 = A 2개 + B 1개 = 3개

주의 사항

• 통증 수치를 0으로 만들지 못하면 -1을 출력해야 합니다.

작성 코드

#include <iostream>
using namespace std;
int main() {
	int a,b;
	int n;
	int rest = 0;
	int sum = 0;
	cin >> n;
	cin >> a >> b;
	if(b > a) {
		int temp = b;
		b = a;
		a = temp;
	}
	sum += n / a;
	rest = n % a;
	while(rest <= n) {
		if(rest % b != 0) {
			rest += a;
			sum--;
		}
		else {
			sum += rest / b;
			rest = 0;
			break;
		}
	}
		if(rest == 0)
			cout << sum << endl;
		else
			cout << -1 << endl;
	}
	```