Codeforces Round 903 (Div. 3) 풀이
이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다.
A. Don't Try to Count
문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다.
#include <bits/stdc++.h>
using namespace std;
bool isSubstr(const s ...
7월 31일 23:32에 게시됨
Codeforces Global Round 27 문제 분석 및 풀이
A번: 빨간 점 제거 후 남은 영역 계산
격자판에서 특정 위치 (r, c)의 빨간 점을 제거했을 때, 나머지 칸들을 세 가지 구역으로 나누어 계산한다. 오른쪽에 있는 열들은 각 행마다 m - c칸만큼 이동하며 영향을 받고, 아래쪽 행 전체는 m * (n - r)만큼 더해진다. 마지막으로 대각선 아래 왼쪽 부분은 (m - 1) * (n - r)로 계산할 수 있다. 최종 답은 이 세 값을 합한 것이 ...
7월 31일 20:29에 게시됨
Codeforces Round 960 (Div. 2) 효율적인 문제 풀이 전략
A. Submission Bait (게임 이론)
앨리스와 밥이 $n$개의 원소를 가진 배열 $a$를 사용하여 게임을 진행합니다. 초기 mx 값은 0이며, 각 플레이어는 자신의 차례에 $a_i \ge mx$인 인덱스 $i$를 선택하여 mx를 $a_i$로 갱신하고 $a_i$를 0으로 만듭니다. 더 이상 움직일 수 없는 플레이어가 패배할 때, 앨리스의 필승 전략 존재 여부를 판별해야 합니다.
이 문제의 핵심은 ...
7월 30일 12:49에 게시됨
Codeforces Round 920 (Div. 3) 효율적인 문제 해결 접근법
Problem A: Square
이 문제는 2차원 평면 위에 놓인 정사각형의 네 꼭짓점 좌표가 주어졌을 때, 해당 정사각형의 넓이를 구하는 문제입니다. 정사각형의 변은 항상 x축 또는 y축에 평행하다는 조건이 있습니다.
네 점의 좌표 중에서 x좌표가 같은 두 점을 찾으면, 그 두 점의 y좌표 차이의 절댓값이 바로 한 변의 길이(a)가 됩니다. 따라서 넓이는 a의 제곱으로 계산할 수 ...
7월 27일 18:21에 게시됨
Codeforces Round #727 (Div. 2) A-D 문제 풀이
A. Contest Start (수학)
이 문제는 패턴을 분석하는 문제입니다. 참가자들의 시작 시간이 일정한 간격으로 배치될 때, 각 참가자가 기다려야 하는 평균 시간을 구해야 합니다.
먼저, 한 참가자가 끝날 때까지 기다리는 다른 참가자의 수를 생각해봅시다.
만약 한 참가자의 경기 시간이 \(t\)이고, 다음 참가자와의 시작 시간 차이가 \(x\)라면, 한 참가자가 경기하는 동 ...
7월 26일 14:19에 게시됨
Codeforces Round 891 Div.3 문제 복기 및 풀이 해설
개요
첫 CF Div.3 대회 참가 후, T2의 문제를 오독하고 T3에서 무리한 구조 설계로 실패한 경험을 바탕으로 복기하며 각 문제를 해석하고 해결 방안을 정리한다.
A. 배열 분할과 합의奇偶성
문제 요약: 주어진 배열을 두 부분으로 나누어 각 부분의 합의 홀짝성이 동일하도록 만들 수 있는지 판단한다.
해석 및 분석: 홀수(odd)와 짝수(even)의 합 연산 규칙은 다음과 같 ...
7월 17일 21:47에 게시됨
Codeforces 2133 문제 분석 및 풀이
C The Nether: DAG에서 최장 경로 탐색
이 문제는 그래프의 구조를 쿼리하는 방식으로 해결하는 인터랙티브 문제입니다. 주어진 방향성 비순환 그래프(DAG)에서 가능한 최대 길이의 경로를 찾아야 하며, 쿼리 제한은 2n번입니다.
핵심 전략은 각 정점에서 시작하는 최장 경로 길이를 미리 계산한 후, 그 중 가장 큰 값을 가진 정점을 시작점으로 삼고, 이후 점차 이어지는 ...
7월 10일 18:44에 게시됨
Codeforces Round 991 (Div. 3) F - 구간 최대公约수와 차분 배열
문제 접근
이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다.
따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다.
방 ...
7월 10일 06:27에 게시됨
다이나믹 프로그래밍 문제 풀이 모음
목차
백준 4933 - 마스터 (선형 DP)
백준 5858 - 황금 검 (선형 DP)
백준 1280 - 닉의 임무 (선형 DP)
USACO 2016 오픈 - 2048 (구간 DP)
백준 2585 - 삼색 이진 트리 (트리 DP)
백준 1441 - 추 저울질 (조합 탐색 + 배낭)
백준 1896 - 서로 공격하지 않음 (비트마스크 DP)
Codeforces 1488E - 회문 쌍 (LIS 응용)
Codeforces 1486D - 최대 중앙값 (이분 탐색)
Codeforces ...
7월 9일 04:00에 게시됨
Codeforces Edu Round 143 A-B 풀이 정리
A번: Two Towers
빨간색(R)과 파란색(B) 블록으로 구성된 두 개의 탑이 주어진다. 한 번의 이동에서는 길이가 2 이상인 탑의 꼭대기 블록을 다른 탑으로 옮길 수 있다. 이동을 통해 두 탑 모두 빨강-파랑이 번갈아 나타나는 형태로 만들 수 있는지 판별하는 문제다.
핵심 관찰
탑의 구조를 분석하면 몇 가지 중요한 사실을 발견할 수 있다:
각 탑 내부에서 인접한 동일 색 ...
7월 5일 00:34에 게시됨