Codeforces Edu Round 143 A-B 풀이 정리
A번: Two Towers
빨간색(R)과 파란색(B) 블록으로 구성된 두 개의 탑이 주어진다. 한 번의 이동에서는 길이가 2 이상인 탑의 꼭대기 블록을 다른 탑으로 옮길 수 있다. 이동을 통해 두 탑 모두 빨강-파랑이 번갈아 나타나는 형태로 만들 수 있는지 판별하는 문제다.
핵심 관찰
탑의 구조를 분석하면 몇 가지 중요한 사실을 발견할 수 있다:
각 탑 내부에서 인접한 동일 색 ...
7월 5일 00:34에 게시됨
Codeforces Round 2204 풀이: A~F번 문제 해설
A. 공 던지기
간단한 시뮬레이션으로 해결할 수 있다. 현재 위치에서 지시에 따라 좌우로 이동하며, 처음 방문하는 지점의 개수를 기록하면 된다.
코드 보기#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
st ...
7월 4일 01:15에 게시됨
세그먼트 트리와 비트셋을 활용한 쿼리 문제 해결 (Codeforces Round #538 Div.2 F)
문제 개요
주어진 배열에서 구간 곱과 그 결과에 대한 오일러 피 함수 값을 계산하는 문제입니다. 핵심 아이디어는 오일러 피 함수의 성질과 300 이하의 소수가 62개뿐이라는 점을 활용하는 것입니다.
수학적 배경
구간 [l, r]의 곱을 X라고 할 때, X를 소인수분해하면 다음과 같습니다:
X = ∏ p_i^{c_i} (i = 1 to n)
오일러 피 함수는 곱셈적 함수이므로:
φ(X) = φ(∏ ...
6월 29일 00:36에 게시됨
Codeforces Round #690 (Div. 3) 풀이
A. Favorite Sequence
길이가 n인 배열 a를 특정 규칙에 따라 재배치하여 배열 b를 만든다. 재배치 규칙은 첫 번째, 마지막, 두 번째, 마지막에서 두 번째, ... 순서로 원소를 선택하는 것이다. 배열 b가 주어졌을 때 원본 배열 a를 복원하는 문제이다.
양쪽 끝에서 중앙으로 이동하는 투 포인터 기법을 적용한다. 왼쪽 포인터는 1부터 시작하고 오른쪽 포인터는 n부터 시 ...
6월 26일 02:34에 게시됨
Codeforces Round #879 Div.2 참가 후기 및 문제 풀이
A번 문제: 부호 조정을 통한 곱의 양수화
배열에 포함된 정수들 중 -1과 1의 개수를 세어, 전체 원소의 곱이 양수가 되도록 최소 연산 횟수를 구하는 문제이다. 핵심은 음수(-1)의 개수가 홀수일 경우 하나를 제거하고 1로 변환해야 한다는 점이다. 이후 1의 개수가 -1의 개수 이상이 될 때까지 두 개씩 변환해 나간다. 이때 매번 두 개의 -1을 1로 바꾸므로 연산 횟수는 2 ...
6월 25일 21:59에 게시됨
Codeforces 632 Div.2 문제 분석 및 해결 전략
A문제: 색칠된 격자판의 조건 만족
크기 n × m의 격자에서 흰색 칸과 검은 칸이 존재하며, 각 칸은 인접한 칸 중 적어도 하나가 다른 색이어야 한다. 요구사항은 검은 칸의 수가 흰 칸보다 정확히 하나 많아야 한다.
직관적인 접근은 모든 칸을 두 가지 유형으로 나누고 조건을 검사하는 것이지만, 이는 복잡하고 비효율적이다.
실제로는 간단한 패턴으로 해결 가능하다. ...
6월 24일 04:38에 게시됨
Codeforces Round 1029 Div.3 A-D번 문제 해설
A. False Alarm
문제의 지시에 따라 직접 구현하면 됩니다. 1이 등장하는 위치들을 기록하고, 인접한 1들 사이의 거리를 누적하여 총 소요 시간을 계산합니다.
정답 코드:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
...
6월 18일 01:45에 게시됨
Codeforces 라운드 187 문제 해설
A. 상자 탑 쌓기
같은 크기의 상자만 존재하므로 각 상자가 견딜 수 있는 최대 상자 수를 계산하면 된다. 이 값을 c로 표기하면, 최대 스택 높이는 c+1이 된다. 전체 상자 수 n을 나누어 최소한의 스택 수를 계산한다.
코드 보기
<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>
using namespace std;
int main() {
...
6월 15일 17:04에 게시됨
Codeforces Round #574 (Div. 2) 기술 블로그 및 문제 풀이
Problem A: Drinks Choosing
N명의 학생들이 각자 선호하는 음료 맛이 있습니다. 총 $\lceil n/2 \rceil$개의 세트가 제공되며, 각 세트에는 같은 맛의 음료 2병이 들어 있습니다. 목표는 최대한 많은 학생이 자신이 원하는 맛의 음료를 받을 수 있도록 배분하는 것입니다.
가장 효율적인 방법은 동일한 맛을 원하는 학생들을 2명씩 묶어 한 세트를 주는 것입니다. 이렇게 ...
6월 14일 17:30에 게시됨
코드포스 알고리즘 최적화: 동적 계획법, 그리디, 서로소 집합을 활용한 문제 풀이
1787C - Remove the Bracket
동적 계획법(DP)을 사용하여 괄호를 제거했을 때의 최소 비용을 계산하는 문제입니다. 각 원소를 특정 임계값 $k$를 기준으로 두 부분으로 나누고, 이전 상태의 최소값을 갱신하는 방식으로 접근합니다. 상태 전이 시 곱셈 연산이 발생하므로, 각 위치에서 0번과 1번 선택지에 따른 누적 비용을 독립적으로 관리하여 최적해를 도출합니다.
#inc ...
6월 5일 21:57에 게시됨