A. Yet Another Tetris Problem
필요한 지식
- 구현
접근
- 최고 높이에서 현재 높이를 뺀 값중 홀수가 하나라도 존재하면
2X1블럭을 아무리 배치해도 모든 블럭을 삭제할 수 없다.
코드(C++)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>v;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
bool flag = true;
int mh = INT_MAX;
for (int i = 0; i < n; i++) {
int x; cin >> x;
v.push_back(x);
mh = min(mh, x);
}
for (int i = 0; i < n; i++) {
v[i] = v[i] - mh;
if (v[i] % 2 == 1) flag = false;
}
if (flag) cout << "YES\n";
else cout << "NO\n";
v.clear();
}
return 0;
}B. Yet Another Palindrome Problem
필요한 지식
- 구현
O(n^2) 접근
-
순서를 고려하여 3개의 원소를 뽑았을 때, 그 3개의 숫자가 팰린드롬인지 확인한다.
-
단순히 N^2도 가능하지만 중간의 원소는 무엇이 와도 상관이 없으므로
i와i+2번째 원소가 같은지 봐주면 된다.
O(n^2) 코드(C++)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>v;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
bool flag = false;
for (int i = 0; i < n; i++) {
int x; cin >> x; v.push_back(x);
}
for (int i = 0; i < v.size() - 2; i++) {
if (flag) break;
for (int j = i + 2; j < v.size(); j++) {
if (v[i] == v[j]) {
flag = true;
break;
}
}
}
if (flag) cout << "YES\n";
else cout << "NO\n";
v.clear();
}
return 0;
}O(n) 접근
- for문으로 순회를 해주면서 현재 값이 2번 전에 나왔던 수라면 팰린드롬이 된다.
O(n) 코드(C++)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
vector<int>v;
bool chk[5001];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
memset(chk, 0, sizeof(chk));
int n; cin >> n;
bool flag = false;
for (int i = 0; i < n; i++) {
int x; cin >> x; v.push_back(x);
}
int pprev = 0, prev = 0;
for (int i = 0; i < v.size(); i++) {
if (flag) break;
chk[pprev] = true;
pprev = prev;
prev = v[i];
if (chk[v[i]]) {
flag = true;
break;
}
}
if (flag) cout << "YES\n";
else cout << "NO\n";
v.clear();
}
return 0;
}C. Frog Jumps
필요한 지식
- 그리디..?
접근
-
최종 목적지인
n+1칸에R이 있다고 생각하고 시작점부터R이적힌 칸과 그다음R이 적힌 칸까지의 거리의 최대값을 구해 출력해 주었다. -
최종 목적지를 포함하여
R이 적힌 칸의 최대거리만큼은 최소로 움직일 수 있어야 도달이 가능하다라는 아이디어였다.
코드(C++)
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
string s; cin >> s;
s += 'R';
int pos = -1;
int tmp = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'R') {
tmp = max(tmp, i - pos);
pos = i;
}
}
tmp = max(tmp, int(s.length()-pos));
cout << tmp << "\n";
}
return 0;
}D. Pair of Topics
필요한 지식
- upper_bound
접근
-
ai - bi > aj - bj인i,j의 경우의 수를 찾아야한다. -
식을 정리하면
(ai - bi) - (aj - bj) > 0로 정리 할 수 있다. -
같은 인덱스 끼리만 뺼셈이 이루어 지니까
bi를 입력받으면서ai에ai-bi한 값을 저장한다. -
이제
(ai - bi) - (aj - bj) > 0이 식은ai - aj > 0로 나타낼 수 있게된다. -
경우의 수를 구해주기 위해 고려해 주어야 할 경우는 크게 두가지로 구분할 수 있다.
1.ai가 양수 인 경우
2.ai가 음수 혹은 0 인경우 -
1.의 경우에는 양수들 중 2개를 선택하는 조합의 수를 더해주면된다.
ans += (n - i) * (n - i - 1) / 2 -
2.의 경우에는
aj가-ai보다 큰 수들의 개수를 더해주면된다. 빠르게 찾아주기 위해upper_bound를 사용했다. -
ans += (n - i) * (n - i - 1) / 2이 수식에서int형으로 연산시 오버플로우가 발생할 수 있다. 이부분 때매 5번이나 틀렸다...
코드(C++)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll>a, b;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n;
ll ans = 0;
for (ll i = 0; i < n; i++) {
ll x; cin >> x; a.push_back(x);
}
for (ll i = 0; i < n; i++) {
ll x; cin >> x; a[i] -= x;
}
sort(a.begin(), a.end());
for (ll i = 0; i < n; i++) {
if (a[i] > 0) {
ans += (n - i) * (n - i - 1) / 2;
break;
}
else ans += (a.end() - upper_bound(a.begin() + i, a.end(), -a[i]));
}
cout << ans;
return 0;
}결과
🦉🦉🦉🦉🦉