하하하하하… B번해서 맞왜틀 때문에 고통스러워 하다가 그냥 제가 멍청했습니다…
배열 범위 초과 런타임 에러 조심…
C번도 쉬워서 B만 빨리 풀었어도 좋았을 텐데 아쉽네요…ㅠ
A. Even Subset Sum Problem
알고리즘
- 완전 탐색
간단한 문제입니다.
모든 부분 수열을 보면서 구간합이 짝수라면 구간을 출력하면 됩니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int n; cin >> n;
int arr[105] = {};
FOR(i, 1, n) cin >> arr[i];
int sum, flag = 0;
FOR(i, 1, n) {
sum = 0, flag = 0;
FOR(j, i, n) {
sum += arr[j];
if (~sum & 1) {
flag = 1;
cout << j - i + 1 << '\n';
FOR(k, i, j) cout << k << ' ';
cout << '\n';
break;
}
}
if (flag) break;
}
if (!flag) cout << -1 << '\n';
}
return 0;
}
B. Count Subrectangles
알고리즘
- 구현
배열 인덱스를 벗어날 때 예외처리를 하지 않아 런타임 에러를 3번 받았습니다…
다행히 나중에라도 풀어서 다행이네요
a, b의 연속되는 1이 나오는 횟수별로 개수를 저장합니다.
그 후에 x * y = k를 만족하는 모든 경우의 a[x] * b[y]를 더하면 됩니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int n, m, k; cin >> n >> m >> k;
ll a[40005] = {}, b[40005] = {};
ll cnt = 0;
FOR(i, 1, n) {
int x; cin >> x;
if (x) a[++cnt]++;
else cnt = 0;
}
cnt = 0;
RFOR(i, n, 1) {
if (a[i] > 0) {
a[i] += a[i + 1];
}
}
cnt = 0;
FOR(i, 1, m) {
int x; cin >> x;
if (x) b[++cnt]++;
else cnt = 0;
}
cnt = 0;
RFOR(i, m, 1) {
if (b[i] > 0) {
b[i] += b[i + 1];
}
}
ll ans = 0;
FOR(i, 1, n) {
if (k % i) continue;
if (k / i > m) continue;
ans += (a[i] * b[k / i]);
}
cout << ans << '\n';
return 0;
}
C. Unusual Competitions
알고리즘
- 스택
여는 괄호와 닫는 괄호를 저장하는 스택을 따로 선언하고 여는 괄호가 나왔을 때 짝이 없는 닫는 괄호가 있다면 그 위치를 바꿔야하니 ans에 더하시면 됩니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int n; cin >> n;
string s; cin >> s;
stack <char> a, b;
int ans = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '(' && b.empty()) a.ep(i);
if (s[i] == '(' && !b.empty()) {
ans += 2;
b.pop();
}
if (s[i] == ')' && a.empty()) b.ep(i);
if (s[i] == ')' && !a.empty()) a.pop();
}
if (a.size() || b.size()) cout << -1 << '\n';
else cout << ans << '\n';
return 0;
}