본문 바로가기

알고리즘

 (9)
Codeforces Round #689 (Div.2) 이틀 전에 있었던 코드포스 라운드 689의 풀이이다. 개인적으로 적절한 그림 등과 함께 깔끔한 문제들이 나왔던 것 같다. 다만, B 문제의 제한을 좀 더 작게 줬으면 더 직관적이었을 것 같다. A. String Generation 단순히 길이가 \(N\)인 \(abcabc...\) 문자열을 출력해주면 된다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) { long long n, k; cin >> n >> k; for (int i = 0; i > M; vectorv; for..
Codeforces Global Round 12 어제 밤부터 진행된 코드포스 글로벌 라운드 12의 풀이이다. A. Avoid Trygub 주어진 문자열을 정렬해 출력하기만 해도 trygub을 없앨 수 있다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { long long N; cin >> N; string str; cin >> str; mapm; for (char i : str)m[i]++; for (int i = 0; i 0) { m[i + 'a']--; cout T; while (T--) { long long N, k; cin >> N >>..
Codeforces Round #687 (Div.2) 어제 있었던 코드포스 라운드 687 풀이이다. 3솔브를 했고, D를 업솔브했다. A. Prison Break \(max( r + c - 2, m - r + c - 1,n - c + r - 1,m - r + n - c )\)가 답이다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { long long m, n, r, c; cin >> m >> n >> r >> c; long long mx = max({ r + c - 2, m - r + c - 1,n - c + r - 1,m - r + n - c }); cout T; while (T--) { long long..
Codeforces Round #686 (Div.3) A. Special Permutation 길이가 \(N\)이면서 모든 \(i\)에 대해 \(arr[i] \ne i\)를 만족하는 수열을 출력하는 문제이다. \( \{2, 3, 4, ... , N, 1\} \)은 주어진 조건을 무조건 만족한다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int N; cin >> N; for (int i = 1; i > in; v[i] = in; m[in]++; } int ans = 0; int ind = 0; for (auto &i : m) { ind++; if (i.second == 1) { ans = i.first;..
Codeforces Round #685 (Div.2) 11월 21일 있었던 코드포스 라운드 685의 풀이이다. A. Subtract or Divide 주어진 수 \(N\)을 두 가지 연산을 이용해 \(1\)로 만드는데, 필요한 연산 횟수의 최솟값을 구하는 문제이다. 두 가지 연산은 각각 수를 자신의 진약수로 나누거나, \(1\)을 빼는 연산이다. 결정적인 관찰은 \(N\)이 짝수이면 1번의 연산만으로 무조건 \(N\)을 \(2\)를 만들 수 있는 것이다. 이것을 늦게 발견해서 이 문제를 푸는 데 25분이나 걸렸다. 시간 복잡도는 테스트 케이스 당 \(O(1)\)이다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--..
Educational Codeforces Round 98 (Div.2) 그저께 밤에 있었던 Educational Codeforces Round 98 풀이이다. 총 3솔브를 했다. A. Robot Program 주어지는 두 길이를 \( N, M \)이라 하자\(( N \ge M )\). 이 때, 아래 그림과 같이 움직이는 게 최선의 경로이며, 총 필요한 Command의 개수는 \(N=M\)일 때 \(2M\)개이고, \(N \neq M\)일 때 \(2N - 1\)개이다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int N, M; cin >> N >> M; if (N < M)swap(N, M); int res = 0; res..
Codeforces Round #684 (Div.2) 어제 있었던 Div.2 코드포스 라운드의 풀이이다. 총 3솔브를 했다. A. Buy the String 이진 수열을 적당히 변환시켜 수열을 구매하는 값을 최소화시키는 문제이다. 0의 가격, 1의 가격, 변환 비용의 대소 비교를 통해 쉽게 문제를 해결할 수 있다. 시간 복잡도는 $O(N)$이다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { long long n, c0, c1, h; string s; cin >> n >> c0 >> c1 >> h; cin >> s; long long cost = 0; if (c0 >= c1) { if (h < c0 - c1..
Codeforces Round #663 (Div.2) A. Suborrays https://codeforces.com/contest/1391/problem/A Problem - A - Codeforces codeforces.com 설명이 엄청나게 장황하게 써 있어서 약 15분 동안 문제를 쳐다만 보고 있었다. 그래서 종이에 써보면서 답을 알게 됐는데, 1 2 3 4 ... N을 출력해도 맞다는 것을 알게 되었다. #include #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) { int N; cin >> N; for (int i = 1; i ..
Codeforces Round #661 (Div.3) A. Remove Smallest https://codeforces.com/contest/1399/problem/A 인자가 n개인 배열을 정렬했을 때 계단수인지 확인한다. 정렬된 인자 사이의 차가 1보다 크면 계단수가 아니다. 시간 복잡도는 O(NlogN)이다. #include #include #include #include #include using namespace std; int t, N; int arr[51]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> N; bool flag = 1; for (int i = 0; i > arr[i]; sort(arr..

티스토리툴바