백준 1214 쿨한 물건 구매 (c++) : 피너클

1214번: 쿨한 물건 구매

https://www.acmicpc.net/problem/1214

 

수학 문제다.

 

문제에서 대충 식을 세우면

D <= aP + bQ

위에 처럼 된다. a와 b는 각자의 수를 곱하는 크기이다.

a가 0이고 b가 0이면 0 * P + 0 * Q인것이다.

 

if (p < q) swap(p, q);

 

무조건 p가 q보다 크게 하기 위해 위의 코드를 돌릴 것이다.

이제부터 P는 모조건 Q보다 크거나 같다.

 

P = Q + c

그러니 P를 위의 식처럼 표현할수 있고

Q = P - c

Q는 위의 식처럼 표현할 수 있다.

 

D <= aP + bQ

이 식으로 돌아가서

D <= aP + b(P - c)

D <= aP + bP - bc

D <= (a + b)P - bc

D <= (a + b)P - b(P - Q)

위 처럼 변경할 수 있다.

 

위의 식에서 bP 와 b(P - Q) 부분을 봐보자

P는 P - Q보다 무조건 크다. 5가 5 - 3 보다 큰건 당연한것이다.

그렇기 때문에

bP - b(P - Q)는 무조건 양수이다.

 

그러면 aP의 값이 중요해 진다. (a + b)P - b(P - Q)의 최솟값은 aP에 의해 정해진다.

여기서 P는 문제에서 주어지는 값이고 우리가 결정하는 값은 a이다.

우리는 a의 범위에 대해 생각해야 한다.

 

가장 간단하게 생각하는건 당연히 D/P이다.

a가 D/P이면 a * P = D/P * P = D이니 바로 D가 되어버리며 최솟값이 나오게 된다.

 

그리고 또 하나가 있는데 a가 Q인 경우이다.

우리는 a * P를 하고 있다.

a가 Q인 경우에는 P를 Q번 곱하는 것이다.

이걸 다르게 말하면

Q를 P번 곱하는 것이다.

P * Q = Q * P

 

b가 P인 경우도 똑같다. b*Q -> P * Q

 

D가 P * Q보다 큰 경우를 생각해보자

D = P * Q + C

C는 정체 불명의 수이다.

 

이 경우에는 

D <= aP + bQ

D <= aP + PQ + bQ

이렇게 생각해볼수있다.

D는 P*Q보다 큰 값이니 오른쪽에 PQ가 있어도 상관 없다.

 

이 PQ는 어디에 붙어도 상관이 없다. aP에 붙어도 되고 bQ에 붙어도 된다.

 

여기가 중요하다.

a에다가 PQ를 붙일바엔 b에다가 PQ를 붙이는게 좋다.

a' = (a + Q)라고 생각하면

D <= aP + bQ

D <= aP + PQ + bQ

D <= (a + Q)P + bQ

D <= a'P + bQ

위와 같이 된다. a'는 Q이상의 수이다. a'P는 aP + QP이다. 

이제 생각해보자.

지금 우리는 D가 P * Q보다 큰 경우에 대해 이야기하고있다.

a'P는 aP + QP이고 bQ는 bQ이다.

D <= aP + QP + bQ인 상황이다.

 

이 상황은 a'가 a+Q가 아닌 a인 상황에서 이미 구해졌다.

이게 뭔소리냐

 

D <= a'P + bQ

여기서 a'는 a이다. a'는 당연히 a + Q보다 작고 오른쪽 항 a'P + bQ에는 PQ가 존재해야한다.

D가 PQ보다 큰 숫자이니

 

그럼 b가 자연스럽게 b + P가 되면 된다.

b' = b + P라고 했을때

D <= aP + b'Q
D <= aP + (b + P)Q
D <= aP + PQ + bQ

위와 같이 된다.

 

우리가 a + Q를 계산하기 전 a를 계산할때 이미 똑같은 식이 계산된 것이다. 중복되는 것이다.

 

이제 코드로 넘어가보자

long long d, p, q;

long long ans = 100000000000;

사용할 변수들이다.

 

	cin >> d >> p >> q;

	if (p < q) swap(p, q);

수들을 입력받아주고 p를 더 크게 해준다.

 

	for (int a = 0; a <= min(q, d / p) + 1; a++) {
		long long num = d - p * a;
		if (num <= 0) {
			ans = min(ans, a * p);
			continue;
		}

		long long b = num / q;
		if (b * q < num) b++;

		ans = min(ans, b * q + a * p);
	}

우리는 a가 0인 경우에서부터 시작한다.

a는 어디까지 가야하는가

D가 P*Q보다 작을때는

D/P가 Q보다 작게 나올 것이다.

 

D가 P*Q보다 클때는 

D/P가 Q보다 크게 나올 것이다.

하지만 a가 Q보다 커지는 순간부터는 이미 이전에 계산된 값들이 사용되는 것이다.

 

그러니 D/P와 Q중 더 작은 수까지 a를 사용하면 된다.

그 다음에는 간단한 수학 과정이니 넘어가겠다.

 

#include <iostream>
#include <algorithm>

using namespace std;

long long d, p, q;

long long ans = 100000000000;

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> d >> p >> q;

	if (p < q) swap(p, q);

	for (int a = 0; a <= min(q, d / p) + 1; a++) {
		long long num = d - p * a;
		if (num <= 0) {
			ans = min(ans, a * p);
			continue;
		}

		long long b = num / q;
		if (b * q < num) b++;

		ans = min(ans, b * q + a * p);
	}

	cout << ans << '\n';

	return 0;

}

전체코드다.