본문 바로가기

문제 풀이

문제 풀이/그외 2021. 7. 17. SCPC 2021 Round 1 작년에 비해 예선 난이도가 쉬워졌다. 1. 친구들 \(N\)명의 사람들이 서 있다. \(i\)번 사람은 자연수 \(D_i\)를 각각 가지고 있는데, \(i\)번 사람과 \(i+D_i\)번 사람이 서로 친구 관계임을 나타낸다. (\(i_D+i > N\)일 경우는 무시한다) A, B가 친구 관계이고 B, C가 친구 관계라면, A, C도 친구 관계이다. 친구 관계의 극대 그룹은 해당 그룹 내의 모든 사람들이 친구 관계이면서, 이 조건을 유지하는 가장 큰 그룹을 말한다. 극대 그룹의 개수를 알아내야 한다. 모든 친구 관계를 그래프의 간선이나 Union-Find등으로 합쳐서, 컴포넌트의 개수를 세면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..
문제 풀이/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 ..
문제 풀이/그외 2021. 3. 28. Code Jam - Qualification Round 2021 Reversort Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 문제에 Reversort이라는 정렬방법이 주어진다. 배열이 주어지면, Reversort를 이용해 정렬하는데 필요한 비용을 구해야 한다. 하라는대로 구현하면 된다. 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..
문제 풀이/그외 2021. 3. 21. Round A 2021 - Kick Start 2021 K-Goodness String Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com \(n\)길이의 문자열 \(s\)가 주어진다. 이 문자열의 점수를 \(s_i \ne s_{n-i+1}\)를 만족하는 \(i\)의 개수라고 하자. (\(1 \le i \le n/2\)) 문자열의 점수를 \(k\)로 만들기 위해, 바꿔야 하는 문자의 최소 개수를 구해야 한다. 주어..

티스토리툴바