문제 개요
네 개의 정수 n, x, y, z가 주어졌다고 가정해 봅시다. 이 정수들을 바탕으로 다음 규칙에 따라 하나의 수열을 생성해야 합니다.
- 수열의 첫 번째 항은 x mod 231 입니다.
- 첫 번째 항을 제외한 나머지 항은 ai = (ai-1 × y + z) mod 231 로 정의됩니다. (단, 1 ≤ i ≤ n-1)
목표는 이렇게 만든 수열에 포함된 서로 다른 정수, 즉 고유한 값의 개수를 구하는 것입니다.
입력 예시
예를 들어 n = 5, x = 1, y = 2, z = 1이 입력으로 주어진다면 출력은 5가 됩니다. 실제로 생성되는 수열의 고유한 값은 {1, 3, 7, 15, 31}이므로 답은 5입니다.
풀이 방법
이 문제는 불린(bool) 배열을 활용해 이미 등장한 값을 추적하는 방식으로 해결할 수 있습니다. 단계별 풀이 과정은 다음과 같습니다.
- MOD를 2^31로 설정합니다.
- 불린 배열 temp를 선언하고 크기를 MOD로 지정합니다.
- p를 x mod MOD로 초기화한 뒤 temp[p]를 true로 표시합니다.
- ans를 1로 초기화합니다. (첫 번째 항은 항상 존재)
- i가 1부터 n-1까지 증가하면서 다음을 반복합니다.
- p를 ((p × y) + z) mod MOD로 갱신합니다.
- temp[p]가 이미 true라면 같은 값이 재등장한 것이므로 반복문을 종료합니다.
- 그렇지 않으면 ans를 1 증가시키고 temp[p]를 true로 설정합니다.
- 최종적으로 ans를 반환합니다.
여기서 핵심 아이디어는 수열 생성 과정에서 어떤 값이 한 번이라도 다시 나타나면 이후에는 항상 동일한 패턴이 반복된다는 점입니다. 따라서 중복 값이 발견되는 순간 반복을 멈추더라도 고유한 값의 개수를 정확하게 구할 수 있습니다.
C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 2147483648;
int solve(int n, long long x, long long y, long long z) {
vector<bool> temp;
temp.resize(MOD);
long long p = x % MOD;
temp[p] = true;
int ans = 1;
for (int i = 1; i < n; ++i) {
p = ((p * y) + z) % MOD;
if (temp[p])
break;
++ans;
temp[p] = true;
}
return ans;
}
int main() {
cout << solve(5, 1, 2, 1) << endl;
return 0;
}입력
5, 1, 2, 1
출력
5
마무리
이 알고리즘은 최악의 경우 O(n)의 시간 복잡도를 가지며, 불린 배열 덕분에 각 값의 등장 여부를 상수 시간에 확인할 수 있습니다. 다만 MOD 크기인 약 21억 개의 슬롯을 저장해야 하므로 메모리 사용량이 상당히 크다는 점은 유의해야 합니다. 수열의 특성상 중복이 발생하면 이후 값은 순환하기 때문에, 조기 종료 조건을 활용하면 실제 연산 횟수를 크게 줄일 수 있다는 장점도 있습니다.