왕자와 용 알고리즘 문제

심심풀이로 왕자와 용 알고리즘 문제를 풀고 있는데 도저히 해결법이 떠오르지 않아 이렇게 도움을 청합니다.

문제는 이렇습니다. 용의 머리는 n 개입니다. 왕자는 마법검을 두개 가지고 있는데 하나는 c1개의 용 머리를 또 다른 하나는 c2개의 용 머리를 자를 수 있습니다.

두개의 마법검으로 용 머리를 모두 자르면 왕자가 승리합니다. 단 용머리를 마법검으로 잘랐는데 모든 머리를 자르지 못 하면 c1 마법검을 썼을 경우 g1, c2 마법검을 썼을 경우 g2 개만큼의 머리가 다시 생겨납니다.

마법검은 자를 머리의 개수가 모자라지 않을 경우에만 사용 할 수 있습니다. 만약 남은 용의 머리 개수가 c1 - 1 이거나 c2 - 1인 경우 왕자는 자신의 머리를 포함해서 마법검을 사용 할 수 있고, 이 경우 승패는 비깁니다.

대략적으로 손쉬운 경우의 수는 해결방법을 찾을 수 있었습니다.

제가 막힌 부분은 하나의 마법검을 사용하면 용 머리 갯수가 늘어나고 또 다른 하나의 마법검을 사용하면 용 머리 갯수가 줄어드는 경우입니다.

이걸 수식으로 다시 풀면 이렇게 될 듯 합니다.

n - c1 = a * (c1 - g1) + b (c2 - g2)

또는

n - c2 = a * (c1 - g1) + b (c2 - g2)

이 식을 만족하는 정수 a, b 가 존재하는지를 적절한 시간내에 알아낼 수 있다면 문제를 풀 수 있을 것 같은데 뽀죡한 해결 방법이 떠오르지 않습니다.

참고로 이 경우 c1 - g1 의 값과 c2 - g2 의 값의 부호는 반대입니다. 하나는 양수, 하나는 음수입니다.

혹시 제가 방향 자체를 잘 못 잡은 것일 수도 있을 듯 한데 그렇다면 다른 해결 방향을 제시 해주셔도 감사하겠습니다.