영어 공부의 필요성을 알았습니다…
문제 이해를 세 문제나 잘못 했었네요 ㅠㅠㅠ
D번은 예제가 안 나와서 보니까 제가 없는 조건을 만들어서 예제가 안 나왔었어요…
다음부터는 문제 이해 확실하게 하고 코딩 시작…!
A. Yet Another Tetris Problem
A - Yet Another Tetris Problem
알고리즘
- 구현
한 열에 2칸씩 들어가기 때문에 빈칸이 짝수라면 YES, 홀수는 NO를 출력합니다.
#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
#define mod 998244353
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int n; cin >> n;
vi v(n + 1);
int Max = 0;
FOR(i, 1, n) {
cin >> v[i];
Max = max(Max, v[i]);
}
int flag = 1;
FOR(i, 1, n) {
if ((Max - v[i]) & 1) flag = 0;
}
cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
B. Yet Another Palindrome Problem
B - Yet Another Palindrome 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
#define mod 998244353
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int n; cin >> n;
vi v(n + 1);
FOR(i, 1, n) cin >> v[i];
int flag = 0;
FOR(i, 1, n) {
FOR(j, i + 2, n) if (v[i] == v[j]) {
flag = 1;
break;
}
if (flag) break;
}
cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
C. Frog Jumps
알고리즘
- 구현
R이 있는 칸에 있어야 도착점으로 나아갈 수 있기 때문에
시작점과 R, R과 도착점, R과 R 사이 거리 중 최댓값을 뛸 수 있어야 도착점에 무사히 도착할 수 있습니다.
#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
#define mod 998244353
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
string s;
cin >> s;
int ans = 0;
int pre = -1;
FOR(i,0,(int)s.size()-1) {
if (s[i] == 'R') {
ans = max(ans, i - pre);
pre = i;
}
}
ans = max(ans, (int)s.size() - pre);
cout << ans << '\n';
}
return 0;
}
D. Pair of Topics
알고리즘
- 이분 탐색
ai - bi + aj - bj > 0이 성립해야 합니다.
a - b를 구한 배열을 정렬을 해줘서 이분 탐색이 가능하게 합니다.
반복문으로 한번 보면서 배열에 두 수의 합이 0이상인 인덱스를 구하고 더해줍니다.
#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
#define mod 998244353
using namespace std;
int main() {
FIO;
int n; cin >> n;
vi v(n);
FOR(i, 0, n - 1) cin >> v[i];
FOR(i, 0, n - 1) {
int x; cin >> x;
v[i] -= x;
}
sort(all(v));
ll ans = 0;
FOR(i, 0, n - 1) {
int idx = upper_bound(all(v), -v[i]) - v.begin();
ans += n - idx;
if (v[i] > 0) ans--;
}
cout << ans / 2 << '\n';
return 0;
}