백준 1214번 쿨한 물건 구매 (c++)

 

솔직히 이런문제 50000문제 풀어도 무슨 의미가 있다 싶다

어짜피 또 다른 정수론 다루면 못맞추는건 매한가지 아닌가?

 

단순 브루트포스인줄 알고 이게 왜 플레5에 박혀있나 싶었지만 시간안에 해결하기 위해서 수학적으로 한번 더 생각해야 하는문제였고 답을 봤는데도 별로 와닿지는 않는다

 

cin >> d >> p >> q;
if (q > p)
{
	swap(p, q);
}
if (d % p == 0 || d % q == 0)
{
	cout << d << endl;
	return 0;
}

 

입력을 받고 p가 항상 큰 값을 가리키도록 처리해준다.

입력받은 지폐가 목표액의 약수이면 즉시 목표액을 만들 수 있으므로 바로 답을 출력한다.

 

ans = (d / p) * p + p;
ll maxi = ans;

ans는 일단 p로만 만들 수 있는 목표액보다 큰 가장 작은 수이다.

maxi는 루프 중 사용할 값이고 ans부터 시작한다.

 

for (int i = 1; i <= maxi / p; i++)
{
	ll current = maxi - (p * i);

	if ((d - current) % q == 0)
	{
		cout << d << endl;
		return 0;
	}
	else
	{
		current += ((d - current) / q) * q + q;
	}

	if (ans == current) break;
	ans = min(ans, current);
}

 기본적으로 D<= nP + mQ 를 구해야하는 문제이기 때문에

ans에서 P 성분을 점점 줄여나가고 그만큼을 Q 성분들로 채워나가며 최솟값을 찾아야한다.

 

for문을 돌며 maxi에서 p * i값을 빼면 현재 채워진 p의 합인 current가 생기고

d - current는 q로 채워야 할 나머지가 된다

이 시점에서 d - current가 q로 나누어 떨어지면 d값을 정확히 만들 수 있다는 뜻이므로 결과를 반환한다.

 

그게 아니라면 마찬가지로 합이 d를 넘도록 남은 공간을 q로 채우고 루프를 돌린다.

이때 초기값 ans와 current가 같다는 뜻은 결과값의 사이클이 생겼다는 뜻이므로 더 루프를 돌 의미가 없다