세 개의 숫자가 주어집니다. 처음 두 숫자의 배수에서 n번째 배수를 찾아야 합니다. 좀 더 명확하게 이해하기 위해 예를 들어 보겠습니다.
입력
x = 2 y = 3 n = 7
출력
10
처음 n ****2의 배수는 2 4 6 8 10 12 14입니다.
처음 n ****3 ****의 배수는 3 6 9 12 15 18 21입니다.
두 배수를 결합하고 정렬하면 2 3 4 6 8 9 10 12 14 15 18 21이 되고 목록에서 n번째 숫자는 10입니다.
알고리즘
- 모든 배수를 저장하기 위해 벡터를 초기화합니다.
- x의 처음 n ****배를 찾아 위 벡터에 더하세요.
- 이제 y의 처음 n배를 구합니다.
- 벡터에 아직 없는 경우 벡터에 추가합니다.
- 배수를 정렬합니다.
- 벡터에서 n번째 배수를 출력합니다.
구현
다음은 위의 알고리즘을 C++로 구현한 것입니다.
#include<bits/stdc++.h>
using namespace std;
int findNthMultiple(int x, int y, int n) {
vector<int> multiples;
for (int i = 1; i <= n; i++) {
multiples.push_back(x * i);
}
sort(multiples.begin(), multiples.end());
for (int i = 1, k = n; i <= n && k; i++) {
if (!binary_search(multiples.begin(), multiples.end(), y * i)) {
multiples.push_back(y * i);
sort(multiples.begin(), multiples.end());
}
}
return multiples[n - 1];
}
int main() {
int x = 2, y = 3, n = 7;
cout << findNthMultiple(x, y, n) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
10