C++로 ax + by = n 방정식을 만족하는 x, y 값 찾는 방법

이 문제에서는 세 개의 정수 a, b, n이 주어지며, 우리의 목표는 ax + by = n을 만족하는 정수 x와 y를 찾는 것입니다.

문제 이해를 위한 예시

입력 : a = 4, b = 1, n = 5
출력 : x = 1, y = 1

해결 접근 방법

가장 간단한 해결 방법은 0부터 n 사이의 값을 하나씩 대입하면서 방정식을 만족하는지 확인하는 것입니다. 이를 위해 방정식을 다음과 같이 변형하여 사용합니다.

x = (n - by) / a
y = (n - ax) / b

x에 해당하는 값을 순차적으로 대입했을 때 나머지 값이 b로 나누어 떨어진다면, 그때의 x와 y가 방정식을 만족하는 해가 됩니다. 만약 조건을 만족하는 값이 존재하지 않는다면 "해가 존재하지 않습니다(No solution)"를 출력합니다.

구현 예제

아래 프로그램은 위에서 설명한 해결 방법의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;

void findSolution(int a, int b, int n){
   for (int i = 0; i * a <= n; i++) {
      if ((n - (i * a)) % b == 0) {
         cout<<i<<" and "<<(n - (i * a)) / b;
         return;
      }
   }
   cout<<"No solution";
}

int main(){
   int a = 2, b = 3, n = 7;
   cout<<"방정식 'ax + by = n'의 x와 y 값은 ";
   findSolution(a, b, n);
   return 0;
}

실행 결과

방정식 'ax + by = n'의 x와 y 값은 2 and 1

코드 설명

위 코드의 findSolution 함수는 반복문을 통해 x 후보 값인 i를 0부터 시작하여 i * a <= n인 범위 내에서 증가시킵니다. 각 단계에서 n - i*a 값이 b로 나누어 떨어지는지 검사하고, 나누어 떨어지면 그 시점의 i를 x로, (n - i*a)/b를 y로 출력한 뒤 함수를 종료합니다. 모든 경우를 확인했음에도 조건을 만족하는 값이 없다면 "No solution"을 출력합니다.

이 알고리즘의 시간 복잡도는 O(n/a)로, 선형 탐색 방식이기 때문에 입력 크기가 작은 경우 효율적으로 동작합니다.