T1: 좋은 수 판별하기
문제는 길이 n의 정수 배열 a가 주어졌을 때, 각 원소 a[i]가 "좋은 수"인지 판단하는 것이다. 여기서 "좋은 수"란, 인덱스가 i보다 작은 세 개의 원소 a[j], a[k], a[l]의 합이 a[i]와 일치하는 경우를 말한다. 단, 같은 인덱스는 중복 사용할 수 없다.
제한 조건이 n ≤ 5000이므로, 최악의 경우 O(n²) 정도의 시간 복잡도를 허용할 수 있다. 따라서 다음과 같은 전략을 사용한다:
- 각 위치 i에 대해, 이전 위치들에서 가능한 두 수의 합을 모두 미리 저장해 둔다.
- 부울 배열
v를 사용하여 특정 합의 존재 여부를 추적한다. 오프셋을 더해 음수 인덱스 문제를 해결한다. a[i] - a[j]값이 이전 두 수의 합으로 등장했는지를 확인함으로써, 세 수의 합으로 표현 가능 여부를 판단한다.
핵심 아이디어는 현재 원소를 기준으로, 그 이전 원소 하나와 두 수의 합을 결합해 세 수의 조합을 효율적으로 검사하는 것이다.
#include <bits/stdc++.h>
using namespace std;
const int OFFSET = 200001;
int n;
long long arr[5005];
bool sumExists[400010];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i];
int result = 0;
for (int i = 1; i <= n; ++i) {
bool found = false;
for (int j = 1; j < i; ++j) {
long long diff = arr[i] - arr[j];
if (diff >= -200000 && diff <= 200000 && sumExists[diff + OFFSET]) {
found = true;
break;
}
}
for (int j = 1; j <= i; ++j) {
long long s = arr[i] + arr[j];
if (s >= -200000 && s <= 200000) {
sumExists[s + OFFSET] = true;
}
}
result += found;
}
cout << result << '\n';
return 0;
}
T2: 'SOS' 패턴 포함 문자열 세기
길이 n의 문자열 중, 서브스트링으로 적어도 세 번 'SOS'를 포함하는 문자열의 개수를 구해야 한다. 이때 각 문자는 오직 하나의 'SOS'에만 사용될 수 있으며, 겹쳐서 계산하지 않는다.
동적 계획법을 활용하여 상태를 아래와 같이 정의한다:
dp[i][c][s]: i번째 자리까지 구성했으며, 지금까지 완성된 'SOS'의 개수가 c(최대 2), 그리고 현재 매칭 진행 상태가 s인 경우의 수.- 상태 s:
- 0: 아무것도 매칭되지 않음 (마지막 문자가 S 아님)
- 1: 마지막 문자가 'S'
- 2: 마지막 두 문자가 'SO'
매칭이 완료되면 (즉, 상태 2에서 'S'가 추가되어 'SOS' 완성), 카운트가 증가하고 상태는 0으로 돌아간다. 이렇게 하면 중복 사용을 방지할 수 있다.
세 번째 'SOS'가 완성되는 순간부터는 나머지 자리에 어떤 문자를 배치하든 유효하므로, 해당 시점의 경우의 수에 26^(남은 자리 수)를 곱해 정답에 누적한다.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long modPow(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;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// dp[i][count][state]
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0)));
dp[0][0][0] = 1;
long long ans = 0;
for (int i = 0; i < n; ++i) {
for (int cnt = 0; cnt < 3; ++cnt) {
for (int state = 0; state < 3; ++state) {
if (!dp[i][cnt][state]) continue;
// 다음 문자가 S가 아닌 경우 (25개)
long long ways = (state == 1) ? 24 : 25; // S로 시작하면 안 되는 경우 제외
(dp[i+1][cnt][0] += dp[i][cnt][state] * ways % MOD) %= MOD;
// 다음 문자가 S인 경우
if (state == 0) {
(dp[i+1][cnt][1] += dp[i][cnt][state]) %= MOD;
} else if (state == 1) {
(dp[i+1][cnt][1] += dp[i][cnt][state]) %= MOD;
} else if (state == 2) {
// SO + S → SOS 완성
int newCnt = min(2, cnt + 1);
if (cnt == 2) {
ans = (ans + dp[i][cnt][state] * modPow(26, n - i - 1)) % MOD;
} else {
(dp[i+1][newCnt][0] += dp[i][cnt][state]) %= MOD;
}
}
}
}
}
cout << ans << '\n';
return 0;
}
T3: 물품 선택 제약 조건 하의 조합 계산
n명의 고객이 각각 A 또는 B 물품을 선택하며, A를 최대 a[i]개, B를 최대 b[i]개 살 수 있다. 한 사람당 반드시 하나의 물품을 최소 1개 이상 구매해야 하고, 전체 중 적어도 c명이 A를 선택해야 한다.
쿼리로 각 고객의 a[i], b[i] 값이 변경되며, 매번 갱신 후 유효한 전체 조합 수를 출력해야 한다.
풀이 전략은 다음과 같다:
- 우선 모든 사람이 자유롭게 선택할 경우의 수는 ∏(a[i] + b[i]).
- 그러나 A를 선택한 사람이 c 미만인 경우는 불가능하므로, 이를 제외해야 한다.
- c가 최대 20이므로, 역방향 배낭 문제(rollback knapsack) 기법을 적용할 수 있다.
배열 f[k]를 "현재까지 정확히 k명이 A를 선택한 경우의 수"로 정의하고, 초기에 전체를 기준으로 DP를 구성한다. 쿼리마다 특정 사람의 정보가 바뀌면:
- 기존 기여도를 역연산으로 제거 (역방향 업데이트)
- 새로운
a[i],b[i]로 다시 반영 - 전체 경우의 수에서 A 선택 인원이 c 미만인 경우의 수를 뺀 값을 출력
역연산은 모듈러 역원을 이용하며, 곱셈의 역연산을 통해 안정적으로 상태를 복구한다.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long modPow(long long base, long long exp) {
long long res = 1;
while (exp) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
int n, c, q;
long long a[100010], b[100010];
long long total = 1;
long long f[21]; // f[i]: exactly i people choose A
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> c;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
fill(f, f + 21, 0);
f[0] = 1;
for (int i = 1; i <= n; ++i) {
total = total * ((a[i] + b[i]) % MOD) % MOD;
for (int j = min(c-1, i); j >= 1; --j) {
f[j] = (f[j] * b[i] + f[j-1] * a[i]) % MOD;
}
f[0] = f[0] * b[i] % MOD;
}
cin >> q;
while (q--) {
int idx;
long long x, y;
cin >> idx >> x >> y;
long long oldA = a[idx], oldB = b[idx];
long long invOldB = modPow(oldB, MOD - 2);
total = total * invOldB % MOD * modPow(oldA + oldB, MOD - 2) % MOD;
total = total * (x + y) % MOD;
// Remove old contribution
f[0] = f[0] * invOldB % MOD;
for (int i = 1; i < c; ++i) {
f[i] = (f[i] - f[i-1] * oldA % MOD + MOD) * invOldB % MOD;
}
// Add new contribution
a[idx] = x; b[idx] = y;
for (int i = c-1; i >= 1; --i) {
f[i] = (f[i-1] * x + f[i] * y) % MOD;
}
f[0] = f[0] * y % MOD;
long long bad = 0;
for (int i = 0; i < c; ++i) bad = (bad + f[i]) % MOD;
long long ans = (total - bad + MOD) % MOD;
cout << ans << '\n';
}
return 0;
}