본문 바로가기

문제 풀이

문제 풀이/Codeforces 2020. 6. 19. Codeforces Global Round 8 A - C+= Problem - A - Codeforces codeforces.com 정수 \(a, b\)가 주어진다. 이 정수들에 다음의 두 가지 연산을 할 수 있다. 1. \(a\) += \(b\) 2. \(b\) += \(a\) 이 때, \(a\)나 \(b\)가 \(n\)보다 크도록 만들기 위한 연산 횟수의 최소값을 구해야 한다. 관찰로 더 작은 수의 크기를 늘리는게 무조건 이득이라는 사실을 알 수 있다. 그러면 전체적인 수의 크기가 지수함수의 형태로 증가하므로, 단순 시뮬레이션으로도 충분히 시간안에 돌아가게 된다. 실제로 최악인 \(a=b=1, n=10^9\)를 넣어도 43번의 연산안에 완료됨으로 확인할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..
문제 풀이/Codeforces 2020. 6. 17. Codeforces Round #650 (Div. 3) A - Short Substrings Problem - A - Codeforces codeforces.com 문자열 \(a\)가 있다. \(b\)는 \(a\)의 연속된 길이 2의 부분문자열을 모두 이어 붙여서 만들어지는데, 주어지는 \(b\)를 이용해 \(a\)를 알아내야 한다. \(b\)의 짝수번째 인덱스에 있는 문자들을 모두 출력한 다음, 맨 마지막 글자를 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= b, sw..
문제 풀이/Codeforces 2020. 6. 8. Codeforces Round #648 (Div. 2) A - Matrix Game Problem - A - Codeforces codeforces.com \(n \times m\) 크기의 격자가 있다. 두 사람이 이 격자에 번갈아가며 말을 놓으려고 하는데, 말을 놓을 때는 같은 행이나 열에 말이 없어야 한다. 말을 더이상 놓지 못하는 사람이 진다. 초기 격자의 상태가 주어졌을 때, 누가 이기는지 알아내야 한다. 현재 말이 놓여있지 않은 행의 개수를 \(r\), 열의 개수를 \(c\)라고 하자. 그러면 말을 \(min(r,c)\)번 놓을 수 있으므로, 이 값이 홀수면 전자가, 짝수면 후자가 승리한다. 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..
문제 풀이/Codeforces 2020. 6. 5. Codeforces Round #647 (Div. 1, Div.2) - Thanks, Algo Muse! A - Johnny and Ancient Computer Problem - A - Codeforces codeforces.com 수 \(a,b\)가 주어진다. \(a\)에 다음과 같은 연산을 해서 \(b\)로 만들 수 있는지, 가능하면 최소 몇번의 연산으로 가능한지 알아내야 한다. 1. 2를 곱한다 2. 4를 곱한다 3. 8을 곱한다 4. 2로 나눠 떨어진다면, 2로 나눈다 5. 4로 나눠 떨어진다면, 4로 나눈다 6. 8로 나눠 떨어진다면, 8로 나눈다 먼저 큰 수가 작은 수로 나눠 떨어지지 않는다면, 불가능하다. 나눠 떨어진다면, 큰 수를 작은 수로 나눈 값을 \(x\)라고 하자. \(x\)가 2의 거듭제곱꼴이 아니라면 불가능하다. 2의 거듭제곱 꼴이라면, \(x = 2^n\)이라고 했을 때, \(\..
문제 풀이/Codeforces 2020. 6. 1. Codeforces Round #646 (Div. 2) A - Odd Selection Problem - A - Codeforces codeforces.com 길이 \(n\)인 배열 \(a\)가 있다. 여기에서 원소 \(x\)개를 골라 합이 홀수가 되도록 할 수 있는지 알아내야 한다. 홀수개의 홀수를 선택할 수 있으면 가능하다. 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 48 49 50 51 52 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll..
문제 풀이/Codeforces 2020. 5. 30. Educational Codeforces Round 88 A - Berland Poker Problem - A - Codeforces codeforces.com \(n\)개의 카드가 있고, 그 중 \(m\)개의 카드는 조커이다. \(k\)명의 플레이어가 게임에 참가한다. 각각의 플레이어는 \(\frac nk\)개의 카드를 가져가게 된다. 조커를 가장 많이 가져간 사람이 이기고, (본인 조커 개수 - 나머지 사람들 중 가장 조커가 많은 사람의 조커 개수) 만큼의 점수를 받는다. \(n,m,k\)가 주어졌을 때, 나올 수 있는 최대 점수를 구해야 한다. 한 사람이 가져갈 수 있는 조커의 개수의 최대값은 \(min(\frac nk, m)\)이다. 남은 사람들이 남은 조커를 최대한 고르게 가져갔을 때 가져갈 수 있는 조커의 최대값을 계산해서 빼면 된다. 1 2 3 4..
문제 풀이/Codeforces 2020. 5. 27. Codeforces Round #645 (Div. 2) A - Park Lighting Problem - A - Codeforces codeforces.com \(n \times m\)크기의 공원이 있다. 한 개의 랜턴을 이용해 \(1 \times 2\)크기의 구역을 밝힐수 있다고 할 때, 공원을 모두 밝히기 위해 필요한 랜턴의 최소 개수를 구해야 한다. 먼저 \(nm\)이 짝수면, 답이 \(\frac{nm}{2}\)임은 자명하다. \(nm\)이 홀수라면, 귀퉁이 한 칸을 제외한 나머지 구역을 \(\frac{nm-1}{2}\)개의 랜턴으로 밝힐 수 있고, 하나의 랜턴을 더 사용해서 남은 한 칸을 밝히면 된다. 따라서 답은 \(\lfloor \frac{nm+1}{2} \rfloor\)이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
문제 풀이/Codeforces 2020. 5. 15. Codeforces Round #642 (Div. 3) A - Most Unstable Array Problem - A - Codeforces codeforces.com 정수 \(n\)과 \(m\)이 주어진다. 길이가 \(n\)이고 원소들의 합이 \(m\)인 수열을 만들려고 한다. 각 원소는 모두 0 이상인 정수이다. 이때 각각의 인접한 원소의 차의 합이 최대값을 알아내야 한다. 먼저 \(n\)이 1일 때 답은 0이고, \(n\)이 2일 때 답이 \(m\)임은 쉽게 알 수 있다. \(n\)이 3 이상일 때는 \(\{0,m,0,0,\cdots\}\) 와 같이 수열을 만들었을 때 \(2m\)이 답이 되고, 이보다 값이 큰 경우는 존재하지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #incl..

티스토리툴바