A. Favorite Sequence
길이가 n인 배열 a를 특정 규칙에 따라 재배치하여 배열 b를 만든다. 재배치 규칙은 첫 번째, 마지막, 두 번째, 마지막에서 두 번째, ... 순서로 원소를 선택하는 것이다. 배열 b가 주어졌을 때 원본 배열 a를 복원하는 문제이다.
양쪽 끝에서 중앙으로 이동하는 투 포인터 기법을 적용한다. 왼쪽 포인터는 1부터 시작하고 오른쪽 포인터는 n부터 시작하여 번갈아가며 원소를 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int len;
cin >> len;
vector<int> seq(len);
for (int &val : seq) cin >> val;
int left = 0, right = len - 1;
while (left < right) {
cout << seq[left++] << ' ' << seq[right--] << ' ';
}
if (left == right) cout << seq[left];
cout << '\n';
}
return 0;
}B. Last Year's Substring
숫자로 구성된 문자열이 주어진다. 최대 하나의 연속된 부분 문자열을 제거하여 "2020"을 만들 수 있는지 판별하는 문제이다.
"2020"은 4글자이므로, 제거 후 남는 문자들은 원본의 접두사와 접미사로 구성된다. 접두사에서 0~4글자, 접미사에서 나머지 글자를 취하는 모든 경우를 검증한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int len;
string str;
cin >> len >> str;
bool possible = false;
const string target = "2020";
for (int prefix = 0; prefix <= 4; ++prefix) {
int suffix = 4 - prefix;
if (str.substr(0, prefix) + str.substr(len - suffix) == target) {
possible = true;
break;
}
}
cout << (possible ? "YES" : "NO") << '\n';
}
return 0;
}C. Unique Number
정수 x가 주어진다. 서로 다른 자릿수를 가진 양의 정수의 자릿수 합이 x가 되도록 할 수 있는지 확인하고, 가능하다면 그 중 최솟값을 출력한다.
서로 다른 자릿수의 합은 최대 9+8+7+6+5+4+3+2+1+0=45이므로 x > 45면 불가능하다. 최솟값을 만들기 위해서는 은 자릿수에 작은 숫자, 낮은 자릿수에 큰 숫자를 배치해야 한다. 따라서 9, 8, 7, ... 순으로 자릿수를 채워나간다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int target;
cin >> target;
if (target > 45) {
cout << -1 << '\n';
continue;
}
string result;
int digit = 9;
while (target > 0) {
int use = min(digit, target);
result += char('0' + use);
target -= use;
--digit;
}
reverse(result.begin(), result.end());
cout << result << '\n';
}
return 0;
}D. Add to Neighbour and Remove
길이 n의 배열에서 인접한 원소끼리 합치는 연산을 반복하여 모든 원소가 동일하게 만들 때, 필요한 최소 연산 횟수를 구한다.
최종적으로 남는 값을 결정하면 문제가 단순화된다. 첫 번째 원소는 오른쪽으로만 확장할 수 있으므로, 첫 번째 그룹의 합을 모든 가능한 경우로 시뮬레이션한다. 각 경우에 대해 나머지 배열을 동일한 합으로 분할할 수 있는지 검증한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int len;
cin >> len;
vector<long long> arr(len);
for (auto &v : arr) cin >> v;
int answer = len - 1;
for (int firstGroup = 1; firstGroup <= len; ++firstGroup) {
long long groupSum = 0;
for (int i = 0; i < firstGroup; ++i) groupSum += arr[i];
long long current = 0;
int groups = 1;
bool valid = true;
for (int i = firstGroup; i < len; ++i) {
current += arr[i];
if (current > groupSum) { valid = false; break; }
if (current == groupSum) {
current = 0;
++groups;
}
}
if (current != 0) valid = false;
if (valid) answer = min(answer, len - groups);
}
cout << answer << '\n';
}
return 0;
}E. Close Tuples
길이 n의 배열에서 크기 m의 부분집합을 선택한다. 선택한 원소들의 최대값과 최소값의 차이가 k 이하인 경우의 수를 계산한다.
배열을 정렬하면 각 원소를 최소값으로 하는 경우를 독립적으로 계산할 수 있다. 이진 탐색으로 a[i] + k 이하인 원소의 개수를 찾고, 조합 공식으로 나머지 m-1개를 선택하는 경우의 수를 더한다.
Easy 버전 (m=3, k=2, 모듈러 없음):
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<int> arr(n);
for (int &v : arr) cin >> v;
sort(arr.begin(), arr.end());
long long total = 0;
for (int i = 0; i < n; ++i) {
int bound = upper_bound(arr.begin(), arr.end(), arr[i] + 2) - arr.begin();
int available = bound - i - 1;
total += 1LL * available * (available - 1) / 2;
}
cout << total << '\n';
}
return 0;
}Hard 버전 (일반적인 m, k, 모듈러 10^9+7):
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 10;
long long fact[MAX], invFact[MAX];
long long power(long long base, long long exp) {
long long res = 1;
while (exp > 0) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
void init() {
fact[0] = 1;
for (int i = 1; i < MAX; ++i) fact[i] = fact[i-1] * i % MOD;
invFact[MAX-1] = power(fact[MAX-1], MOD - 2);
for (int i = MAX - 2; i >= 0; --i) invFact[i] = invFact[i+1] * (i+1) % MOD;
}
long long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int tc;
cin >> tc;
while (tc--) {
int n, m, k;
cin >> n >> m >> k;
vector<int> arr(n);
for (int &v : arr) cin >> v;
sort(arr.begin(), arr.end());
long long answer = 0;
for (int i = 0; i < n; ++i) {
int pos = upper_bound(arr.begin(), arr.end(), arr[i] + k) - arr.begin();
int candidates = pos - i - 1;
answer = (answer + nCr(candidates, m - 1)) % MOD;
}
cout << answer << '\n';
}
return 0;
}F. The Treasure of The Segments
n개의 구간이 주어진다. 일부 구간을 제거하여 남은 구간들 중 어느 한 구간이 나머지 모든 구간과 교차하도록 만들 때, 제거해야 하는 최소 구간 수를 구한다.
구간 [L,R]가 다른 구간 [l,r]와 교차하지 않으려면 r < L 또는 l > R이어야 한다. 각 구간을 기준으로 왼쪽에 끝나는 구간 수와 오른쪽에 시작하는 구간 수를 이진 탐색으로 계산하여, 교차하지 않는 구간의 총합을 구한다. 전체에서 이 값의 최솟값이 정답이다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<pair<int,int>> segs(n);
vector<int> lefts, rights;
for (auto &[l, r] : segs) {
cin >> l >> r;
lefts.push_back(l);
rights.push_back(r);
}
sort(lefts.begin(), lefts.end());
sort(rights.begin(), rights.end());
int result = n - 1;
for (auto &[L, R] : segs) {
int endBefore = lower_bound(rights.begin(), rights.end(), L) - rights.begin();
int startAfter = n - (upper_bound(lefts.begin(), lefts.end(), R) - lefts.begin());
result = min(result, endBefore + startAfter);
}
cout << result << '\n';
}
return 0;
}