A에서 말려서 멘탈 관리가 안됐었는데
다행히 B, C를 풀었습니다.
문제가 안 풀리더라도 멘탈 관리 할 수 있도록 노력해야겠네요.
A. Sum of Odd Integers
알고리즘
- 수학
N을 K분할하여 N/K를 K개로 만들고 나머지 값을 추가하여 분배합니다.
N//K를 기준으로 하나는 1 ~ N/K, 다른 하나는 N/K ~ N로 만들어 줍니다. 합은 동일해야 합니다.
그렇게 나눴을 때 중복되는 수가 없으면 YES, 아니면 NO를 출력하면 됩니다.
N, K를 이용하여 경우들을 다 예외처리 하였습니다.
다른 방법이 있을 수 있지만 A번이 이런 예외처리가 나올까해서 다른 방법을 고민했었는데
A번이라서 더 쉽다고 생각하지 않는 습관을 들여야겠네요
#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
#define EPS 1e-9
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int flag = 1;
int n, k; cin >> n >> k;
if (n % k) {
int x = n / k;
int y = n % k;
if (x & 1 && y & 1) flag = 0;
if (~x & 1 && (k - y) & 1) flag = 0;
if (x < k)flag = 0;
}
else {
int x = n / k;
if (x < k) flag = 0;
if (~x & 1) {
if (k & 1) flag = 0;
}
}
cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
B. Princesses and Princes
알고리즘
- 완전 탐색
- 구현
문제에서 말한 그대로 구현하시면 됩니다.
공주와 짝이 없는 왕자 중에 번호가 가장 작은 왕자와 연결을 해주고
짝이 없는 공주와 왕자가 있다면 IMPROVE 아니라면 OPTIMAL을 출력하면 됩니다.
#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
#define EPS 1e-9
using namespace std;
int main() {
FIO;
int t; cin >> t; while (t--) {
int n; cin >> n;
map <int, int> a;
vi v;
FOR(i, 1, n) a[i] = 1;
FOR(i, 1, n) {
int k; cin >> k;
int chk = 0;
FOR(i, 1, k) {
int x; cin >> x;
if (!chk && a.find(x) != a.end()) {
a.erase(a.find(x));
chk = 1;
}
}
if (!chk) v.eb(i);
}
int chk = 0;
for (int i : v) {
if (a.size()) {
cout << "IMPROVE" << '\n';
cout << i << ' ' << a.begin()->fs << '\n';
chk = 1;
break;
}
}
if(!chk) cout << "OPTIMAL\n";
}
return 0;
}
C. Game with Chips
알고리즘
- 구현
A~C 중에 제일 쉬웠던 것 같습니다.
각 칩마다 한 번은 원하는 곳에 도착을 해야합니다.
그리고 그 동작은 2MN 안에 하면 됩니다.
그렇다면 칩들을 일단 가장 위, 왼쪽에 모은 후에 맵 전체를 돌아도 2MN 안에 할 수 있습니다.
M + N - 2 + MN - 1의 연산으로 할 수 있겠네요.
#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
#define EPS 1e-9
using namespace std;
int main() {
FIO;
int n, m, k; cin >> n >> m >> k;
int a, b;
FOR(i, 1, k * 2) cin >> a >> b;
cout << n + m - 3 + n * m << '\n';
FOR(i, 1, n - 1) cout << 'U';
FOR(i, 1, m - 1) cout << 'L';
FOR(i, 1, n) {
if (i & 1) FOR(j, 1, m - 1) cout << 'R';
else FOR(j, 1, m - 1) cout << 'L';
if(i < n) cout << 'D';
}
return 0;
}