본문 바로가기

문제 풀이/Codeforces

문제 풀이/Codeforces 2021. 6. 26. Codeforces Round #728 (Div.1, Div. 2) A - Pretty Permutations Problem - A - Codeforces codeforces.com \(n\)마리의 고양이와 \(n\)개의 집이 있다. \(i\)번째 고양이는 \(i\)번째 집에 살고 있다. 모든 고양이가 원래 살던 곳이 아닌 집에 가서 살려고 할 때, 고양이의 이동 거리의 합의 최소값을 구해야 한다. \(n\)이 짝수면, 인접한 2마리씩 짝지어 집을 교환하면 된다. \(n\)이 홀수면, 첫 3마리를 서로 바꿔 준다음, 나머지를 짝수일 때 방법으로 처리하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; typedef long long ll; type..
문제 풀이/Codeforces 2021. 4. 24. Codeforces Round #718 (Div. 1 + Div. 2) A - Sum of 2050 Problem - A - Codeforces codeforces.com 어떤 수가 \(2050 \cdot 10^k\)꼴로 나타내어지면 이를 2050-수라고 하자. 양의 정수 \(n\)을 가장 적은 개수의 2050-수의 합으로 나타내려면 몇 개가 필요한지 알아내야 한다. \(n\)이 2050으로 나누어 떨어지지 않으면 일단 불가능하다. 가능하다면, 2050으로 나누었을 때 몫의 모든 자릿수의 숫자의 합을 다 더하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include using namespace std; typedef long lon..
문제 풀이/Codeforces 2021. 4. 18. Codeforces Round #715 (Div.1, Div. 2) A - Average Height Problem - A - Codeforces codeforces.com \(n\)길이의 수열 \(a\)가 주어진다. 이 수열의 수를 재배열해서, 연속된 두 원소의 평균이 정수가 되는 경우가 최대가 되도록 했을 때, 그 개수를 구해야 한다. 짝수끼리, 홀수끼리 모으면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); retur..
문제 풀이/Codeforces 2021. 4. 4. Codeforces Round #712 (Div1, Div. 2) A - Déjà Vu Problem - A - Codeforces codeforces.com 문자열 \(s\)가 주어진다. \(s\)의 임의의 위치에 문자 'a'를 추가하여, \(s\)가 팰린드롬이 아니도록 만들어야 한다. \(s\)가 'a'로만 이루어져 있다면 불가능하다. 그렇지 않다면, \(s\)의 맨 앞이나 맨 뒤에 'a'를 추가하면 둘 중 하나는 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include using namespace std; typedef long long ll; typedef pair pii; typedef pa..
문제 풀이/Codeforces 2021. 3. 30. Codeforces Round #711 (Div. 2) A - GCD Sum Problem - A - Codeforces codeforces.com 어떤 수 \(x\)의 gcdSum을 \(x\)와, \(x\)의 모든 자릿수의 합의 최대공약수로 정의하자. \(n\)이 주어지면, \(n\)보다 크거나 같으면서 gcdSum이 1보다 큰 가장 작은 수를 구해야 한다. 어떤 수 \(x\)가 3으로 나눠 떨어진다면, gcdSum도 3의 배수이다. 따라서 \(n, n+1, n+2\)중 하나가 답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; typedef long ..
문제 풀이/Codeforces 2021. 3. 20. Educational Codeforces Round 106 A - Domino on Windowsill Problem - A - Codeforces codeforces.com \(2 \times n\)크기의 격자가 있다. 첫번째 열의 첫 \(k_1\)개 칸과 두번째 열의 첫 \(k_2\)개 칸이 흰색으로 칠해져 있고, 그 외의 칸은 검은색으로 칠해져 있다. \(w\)개의 흰색 도미노와 \(b\)개의 검은색 도미노가 있다. 도미노의 크기는 모두 \(2 \times 1\)이고, 두 칸의 도미노의 색과 격자의 칸이 모두 같으면 그곳에 도미노를 놓을 수 있다. 도미노를 겹쳐서 놓을 수는 없을 때, 모든 도미노를 격자에 놓는 것이 가능한지 알아내야 한다. 관찰을 잘 하면, 각 색깔의 도미노의 면적보다 격자의 면적이 더 작지만 않으면 무조건 가능하다는 것을 알 수 있다. ..
문제 풀이/Codeforces 2021. 3. 18. Codeforces Round #708 (Div. 2) A - Meximization Problem - A - Codeforces codeforces.com \(n\)길이의 배열 \(a\)가 주어진다. 이 \(a\)의 원소들의 순서를 재배열해서, 모든 prefix의 MEX값의 합이 최대가 되도록 해야 한다. 큰 MEX값이 최대한 빨리 나와야 함을 알 수 있다. 앞에서부터 \(a_i = i\) (0-index)가 되도록 최대한 수를 채우면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; typedef long lon..
문제 풀이/Codeforces 2021. 3. 14. Codeforces Round #707 (Div. 1, Div. 2) A - Alexey and Train Problem - A - Codeforces codeforces.com 하라는 대로 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; } int n; int a[101], b[101]; int tim[101]; int main() { ios::sync_..

티스토리툴바