Problem G 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1538/problem/G

이 문제를 푸는데 1주일이 넘게 걸렸던 것 같다.

결국 선형 계획법의 Simplex 방법을 이용해서 풀게 되었다.

( 해당 개념은 구글링을 통해 확인할 수 있다. )


x = red candy 개수

y = blue candy 개수

a = gift set 하나를 만드는데 필요한 red candy or blue candy 개수

b = gift set 하나를 만드는데 필요한 red candy or blue candy 개수


즉,

red candy a 개, blue candy b 개를 담거나

red candy b 개, blue candy a 개를 담아서 2가지 방법으로 gift 하나를 만들 수 있다.

red candy 인지 blue candy 인지는 중요하지 않기 때문에 x < y, a < b가 되도록 값을 설정한다.


여기서 선형 계획법을 쓰기 전에

x / a <= y / b인 경우에는 무조건 x / a 값이 최대 개수이다.

왜냐하면 보통 세트를 최대한 만들려고 할 때 큰 개수에서 큰 개수를 담는다.

y에서 최대한 b씩 담고 x에서 최대한 a씩 담은 후 세트 1개씩 담는 개수를 맞바꾼다면 바꿀 때마다 y는 +(b-a)가 될 거고 x는 -(b-a)가 된다.

맞바꾸다가 세트가 만들어질 수 있는 만큼 개수가 생긴다면 세트를 추가하는 방식으로 세트를 만들면 최대 개수를 만들 수 있게 된다. 

하지만 x / a <= y / b인 경우는 최대한 세트를 만들고 남은 x의 개수는 y의 개수보다 적기 때문에 최대 개수는 x / a 일 수밖에 없다.


[ 선형 계획법 Simplex method 적용 ]

y에서 a 만큼 담고 x에서 b 만큼 담는 방법으로 만든 gift set의 개수를 c,

y에서 b 만큼 담고 x에서 a 만큼 담는 방법으로 만든 gift set의 개수를 d라고 할 때

c + d = f의 최댓값을 구해야 한다.

조건식은

ac + bd <= y

bc + ad <= x

로 설정한다.

ac + bd <= x가 아닌 위의 조건식으로 설정하는 이유는 Simplex 방법을 실행할 때 어떤 입력값이든 축이 되는 행을 정하는 과정에서 항상 같은 방식으로 아래 행을 먼저 기준 행으로 잡고 다음에 위의 행을 기준 행으로 잡기 위함이다.


여유 변수까지 설정하여 정렬하면

ac + bd + u            = y

bc + ad +    + v      = x

-c  -d               + f = 0

이 된다.


Simplex 방법을 사용해 계산을 해보면

u와 v가 0일 때 f가 최대인 것을 알 수 있고

c = ( b*x - a*y ) / ( b*b - a*a )

d = ( b*y - a*x ) / ( b*b - a*a )

이 된다.

x, y, a, b를 대입하면 c와 d의 값을 구할 수 있다.

하지만 이렇게 계산할 경우 test case중 틀리는 case가 생긴다.

정확한 이유는 모르겠지만 여러가지 케이스를 대입해 본 결과,

c와 d의 값이 나누어 떨어지지 않고 소수값이 나오는 경우에 1set가 더 만들어지는 경우가 생겼다.

그래서 구한 c와 d에 버림 계산을 적용하여

x -= (bc + ad)

y -= (ac + bd)

해당 수량만큼 x와 y에서 빼고 나머지 x, y에서 세트가 만들어질 수 있는지 한번 더 확인하여 답을 구했다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        long long x, y, a, b;
        cin >> x >> y >> a >> b;
 
        if (x > y)
            swap(x, y);
        if (a > b)
            swap(a, b);
 
        if (a == b) {
            cout << min(x / a, y / a) << endl;
            continue;
        }
 
        if (x / a <= y / b) {
            cout << x / a << endl;
            continue;
        }
 
        long long c = (((long double)b * x - a * y) / (b * b - a * a));
        long long d = (((long double)b * y - a * x) / (b * b - a * a));
 
        x -= (b * c + a * d);
        y -= (a * c + b * d);
 
        long long answer = c + d;
 
        if (min(x / a, y / b) > 0)
            answer += min(x / a, y / b);
        else if (min(x / b, y / a) > 0)
            answer += min(x / b, y / a);
 
        cout << answer << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기