CSP 제4회 모의고사 후기
이번 모의고사는 첫째 날 치러진 시험이었는데, 네 가지 사고력을 요구하는 문제가 등장했다. 각 문제의 풀이 과정을 정리해보았다.
문제 1: ARC125C - LIS를 원래 순열로 복구하기
주어진 수열에서 최장 증가 부분 수열(LIS)의 길이를 복원하여 사전식 순서가 가장 작은 원래 수열을 구하는 문제다. 핵심 아이디어는 그리디 알고리즘에 있다.
핵심 풀이 전략
수열을 두 그룹으로 나눈다. 하나는 입력으로 주어진 수들의 집합이고, 나머지는 입력에 포함되지 않은 수들의 집합이다. 그리고 LIS의 마지막 원소 a_k(k>1)를 기준으로 왼쪽과 오른쪽으로 분리하여 처리한다.
왼쪽 구간을 처리할 때는 다음 원칙을 따른다. 어떤 수 x가 a_i보다 작다면, x를 a_i 앞에 배치하면 LIS의 길이가 증가하므로 절대 배치할 수 없다. 따라서 x는 반드시 a_i 뒤에 위치해야 한다. 만약 여러 개의 작은 수를 a_i 뒤에 순서대로 배치하면 LIS가 길어지고, 역순으로 배치하면 사전식 최소 조건을 위배한다. 결과적으로 a_i 뒤에는 오직 하나의 작은数만 배치할 수 있다.
오른쪽 구간은 약간의 트릭이 필요하다. a_k보다 큰 수를 a_k 뒤에 배치하면 LIS 길이가 늘어나므로, a_k 뒤에 오는 모든 수는 반드시 a_k보다 작아야 한다. 따라서 남은 수들을 정렬하여 역순으로 출력하면 된다.
구현 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> given(k + 1);
for (int i = 1; i <= k; ++i) {
cin >> given[i];
}
vector<int> remaining;
int currentIdx = 1;
for (int i = 1; i <= n; ++i) {
if (currentIdx <= k && i == given[currentIdx]) {
++currentIdx;
} else {
remaining.push_back(i);
}
}
int pos = 0;
for (int i = 1; i < k; ++i) {
cout << given[i] << " ";
if (pos < (int)remaining.size() && remaining[pos] < given[i]) {
cout << remaining[pos] << " ";
++pos;
}
}
if (pos < (int)remaining.size()) {
bool printedLast = false;
for (int i = (int)remaining.size() - 1; i >= pos; --i) {
if (!printedLast && given[k] > remaining[i]) {
cout << given[k] << " ";
printedLast = true;
}
cout << remaining[i] << " ";
}
if (!printedLast) {
cout << given[k] << endl;
}
} else {
cout << given[k] << endl;
}
return 0;
}
문제 2: ARC125D - 고유한 부분 수열
이 문제는 수열에서 중복되지 않는 모든 부분 수열의 개수를 세는 것이다. 동적 계획법과 Fenwick Tree를 결합하여 O(n log n) 시간에 해결할 수 있다.
동적 계획법 설계
각 위치 i에서 끝나는 고유한 부분 수열의 개수를 f[i]라고 정의한다. 같은 값을 가진 이전 위치 same[i]를 추적하여, 중복을 방지한다. Fenwick Tree를 사용하여 구간 합을 효율적으로 계산한다.
핵심 점화식은 다음과 같다. 만약 현재 위치 i의 값이 이전에 등장한 적이 있다면(same[i] ≠ 0), f[i]는 (i-1)까지의 모든 경우에서 same[i] 이전의 경우를 제외한 값이 된다. 이렇게 하면 중복되는 부분 수열을 제외할 수 있다.
반면 처음 등장하는 값이라면, f[i]는 i-1까지의 모든 경우에 자기 자신만 추가한 경우를 더한 (Tree.Query(i-1) + 1)이 된다. 여기서 1은 현재 원소만으로 구성된 부분 수열을 의미한다.
구현 코드
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const long long MOD = 998244353;
class Fenwick {
private:
int n;
vector<long long> tree;
int lowbit(int x) {
return x & (-x);
}
public:
Fenwick(int n) : n(n), tree(n + 1, 0) {}
void add(int idx, long long val) {
while (idx <= n) {
tree[idx] = (tree[idx] + val) % MOD;
idx += lowbit(idx);
}
}
long long sum(int idx) {
long long res = 0;
while (idx > 0) {
res = (res + tree[idx]) % MOD;
idx -= lowbit(idx);
}
return res;
}
};
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> lastPos(n + 1, 0);
vector<int> prevSame(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] <= n) {
prevSame[i] = lastPos[a[i]];
lastPos[a[i]] = i;
}
}
Fenwick bit(n);
vector<long long> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
if (prevSame[i] != 0) {
long long valid = (bit.sum(i - 1) - bit.sum(prevSame[i] - 1) + MOD) % MOD;
dp[i] = valid;
bit.add(prevSame[i], -dp[prevSame[i]]);
} else {
dp[i] = (bit.sum(i - 1) + 1) % MOD;
}
bit.add(i, dp[i]);
}
cout << (bit.sum(n) + MOD) % MOD << endl;
return 0;
}
문제 3: ARC126C - GCD 최대화
주어진 수열의 모든 원소에 값을 더하여 전체수의 최대공약수(GCD)를 최대화하는 문제다. 추가할 수 있는 총량은 k로 제한된다.
解题 전략
먼 가장 큰 원소까지 모두 통일하는 경우를 확인한다. 이때 필요한 총량이 k 이하라면, 남은 양을 균등하게 분배하여 최종 값을 구할 수 있다.
그렇지 않은 경우, 가능한 GCD 후보를 역순으로 탐색한다. 각 후보 g에 대해, 수열을 구간 [0, g], (g, 2g], (2g, 3g], ... 로 나누고, 각 구간의 원소들을 구간 끝값으로 통일하는 데 필요한 비용을 계산한다. 이 비용이 k 이하인 첫 번째 g가 정답이 된다.
구현 코드
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
long long k;
cin >> n >> k;
vector<int> arr(n + 1);
int maxVal = 0;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
maxVal = max(maxVal, arr[i]);
}
vector<int> bucket(maxVal * 2 + 2, 0);
for (int i = 1; i <= n; ++i) {
bucket[arr[i]]++;
}
vector<int> prefixCount(maxVal * 2 + 2, 0);
vector<long long> prefixSum(maxVal * 2 + 2, 0);
for (int i = 1; i <= maxVal * 2; ++i) {
prefixCount[i] = prefixCount[i - 1] + bucket[i];
prefixSum[i] = prefixSum[i - 1] + 1LL * bucket[i] * i;
}
long long costToMax = 0;
for (int i = 1; i <= n; ++i) {
costToMax += (maxVal - arr[i]);
}
if (costToMax <= k) {
cout << maxVal + (k - costToMax) / n << endl;
return 0;
}
for (int g = maxVal; g >= 1; --g) {
long long totalCost = 0;
for (int j = 1; (j - 1) * g <= maxVal; ++j) {
int left = (j - 1) * g;
int right = j * g;
int count = prefixCount[right - 1] - prefixCount[left];
long long sum = prefixSum[right - 1] - prefixSum[left];
totalCost += 1LL * count * right - sum;
}
if (totalCost <= k) {
cout << g << endl;
return 0;
}
}
return 0;
}
문제 4: ARC126D - 순수 연속 수열
이 문제는 1부터 k까지의 각 수가 정확히 한 번씩 등장하도록 수열을 재배열하는 최소 비용을 구한다. k가 최대 16이므로 상태 압축 동적 계획법을 적용할 수 있다.
상태 정의와 전이
dp[i][S]를 i번째 원소까지 처리했을 때 선택된 수들의 집합이 S인 최소 비용으로 정의한다. 현재 원소 a_i를 선택하거나 선택하지 않는 두 가지 경우를 고려한다.
a_i를 선택하면, 현재 선택된 집합에서 a_i보다 큰 원소들의 개수만큼 비용이 추가된다. a_i를 선택하지 않으면, 이미 선택된 원소들과 아직 선택되지 않은 원소들 중 현재 위치로 이동해야 하는 원소들의 최소값을 선택한다. 이는 이미 정렬된 두 그룹을 서로 가까이 이동시켜 최소 비용을 만드는 방식이다.
구현 코드
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
const int INF = INT_MAX / 2;
vector<int> dp(1 << k, INF);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
int bitMask = 1 << (arr[i] - 1);
int largerMask = bitMask - 1;
for (int state = (1 << k) - 1; state >= 0; --state) {
if ((state & bitMask) == 0) {
int largerCount = __builtin_popcount(state & (~largerMask));
dp[state | bitMask] = min(dp[state | bitMask], dp[state] + largerCount);
}
int selected = __builtin_popcount(state);
int notSelected = k - selected;
dp[state] = min(dp[state], dp[state] + min(selected, notSelected));
}
}
cout << dp[(1 << k) - 1] << endl;
return 0;
}
총평
이번 모의고사에서 네 문제 중 세 문제는 충분히 해결 가능한 수준이었으나, 마지막 문제는考场에서 상태 압축 DP를 떠올리지 못하여 아쉬웠다. 이후 다른 분들의 풀이를 참고하여 이해할 수 있었다. 평소 다양한 동적 계획법 패턴을 연습하는 것이 중요함을 느꼈다.