두 등차수열의 첫 번째 충돌 지점을 찾는 C++ 프로그램

이 글에서는 두 수열이 처음으로 만나는 지점, 즉 두 수열이 공통으로 가지는 첫 번째 값을 찾는 프로그램을 다룹니다.

문제에서는 다섯 개의 변수 'a', 'b', 'c', 'd', 'n'이 주어집니다. 이 값들을 이용해 각각 n개의 항을 가지는 두 개의 등차수열을 만들어야 합니다.

b, b+a, b+2a, …, b+(n-1)a
d, d+c, d+2c, …, d+(n-1)c

그런 다음, 이 두 수열이 공통으로 포함하는 첫 번째 값을 찾으면 됩니다.

해결 접근 방법

이 문제를 해결하려면 먼저 첫 번째 수열의 항들을 하나씩 생성합니다. 그리고 각 항에 대해 다음 두 가지 조건을 검사합니다.

• 해당 값이 두 번째 수열의 첫 항 'd'보다 크거나 같은지
• 그 값에서 'd'를 뺀 차이가 공차 'c'로 나누어 떨어지는지

두 조건을 모두 만족한다면, 그 값은 두 번째 수열에도 존재하는 것이므로 현재 값이 곧 첫 번째 충돌 지점이 됩니다. 모든 항을 검사했는데도 조건을 만족하는 값이 없다면, 두 수열 사이에는 충돌 지점이 존재하지 않는 것입니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
void calc_series(int a, int b, int c, int d, int n) {
    int x, flag = 0;
    // 첫 번째 수열의 항들을 생성
    for (int i = 0; i < n; i++) {
        x = b + i * a;
        // 두 번째 수열에 존재하는지 검사
        if ((x - d) % c == 0 and x - d >= 0){
            cout << "First collision point : "<< x << endl;
            flag = 1;
            break;
        }
    }
    if(flag == 0) {
        cout << "No collision point exists" << endl;
    }
}
int main() {
    int a = 16;
    int b = 9;
    int c = 23;
    int d = 19;
    int n = 78;
    calc_series(a, b, c, d, n);
    return 0;
}

출력 결과

First collision point : 249

위 예제에서 첫 번째 수열은 9부터 시작해 공차 16씩 증가하고, 두 번째 수열은 19부터 시작해 공차 23씩 증가합니다. 두 수열이 처음으로 일치하는 값은 249이며, 프로그램은 이를 정확히 출력합니다.