AtCoder 그랜드 콘테스트 문제 풀이
AGC001
B - 신비한 빛
문제에서 설명하는 그림을 통해, 빛에 의해 형성된 첫 번째 큰 삼각형의 변의 길이는 \(x\), 다음에 형성되는 작은 삼각형의 변의 길이는 \( (n-2x) \)로 관찰됩니다.
분할 정복 접근법으로, 각 단계에서 큰 삼각형의 변 길이를 \( n \), 현재 삼각형의 변 길이를 \( x \)로 설정하면 다음 삼각형의 변 길이는 \( (n - 2x) \)로 계산됩니다. 이는 두 ...
9월 25일 05:57에 게시됨
소인수 개수의 최대공약수 계산: 누적합과 펜윅 트리 적용
문제 분석 및 접근
주어진 데이터 크기를 고려하면 사전에 연산을 수행하는 전처리 과정이 필수적이며, 각 질의는 O(log N) 이하의 시간 복잡도로 처리해야 합니다. 함수 F(x)를 x의 서로 다른 소인수의 개수라고 할 때, 입력의 최댓값이 1,000,000이므로 1 ≤ F(x) ≤ 7의 범위를 가짐을 수학적으로 유도할 수 있습니다. 따라서 임의의 구간 [L, R]에 대해 F(x) 값이 1부터 ...
8월 24일 04:46에 게시됨
CSP2019 Day2T2 분할 최적화
기본적인 동적계획법 접근은 dp[i][j]를 마지막 분할 지점이 i, 이전 분할 지점이 j일 때의 최소 비용으로 정의한다. 누적합을 sum[i] = Σk=1i a[k]로 두면, 전이식은 다음과 같다:
dp[i][j] = min{ dp[j][k] + (sum[i] - sum[j])² }
( sum[i] - sum[j] ≥ sum[j] - sum[k] )
조건를 정리하면 sum[k] ≥ 2×sum[j] - sum[i]가 되며, 고정된 j에 대해 i가 증가함에 따라 하한 ...
7월 7일 02:24에 게시됨
Codeforces 632 Div.2 문제 분석 및 해결 전략
A문제: 색칠된 격자판의 조건 만족
크기 n × m의 격자에서 흰색 칸과 검은 칸이 존재하며, 각 칸은 인접한 칸 중 적어도 하나가 다른 색이어야 한다. 요구사항은 검은 칸의 수가 흰 칸보다 정확히 하나 많아야 한다.
직관적인 접근은 모든 칸을 두 가지 유형으로 나누고 조건을 검사하는 것이지만, 이는 복잡하고 비효율적이다.
실제로는 간단한 패턴으로 해결 가능하다. ...
6월 24일 04:38에 게시됨
USACO 2022년 11월 대회 문제 풀이: 외톨이 사진과 단어 맞추기
문제 1: 외톨이 사진(Lonely Photo)
농장주 존이 N마리의 소를 새로 샀다. 각 소는 게른지(Guernsey) 또는 홀스틴(Holstein) 품종이다. 소들이 한 줄로 서 있을 때, 길이가 3 이상인 모든 연속 구간에 대해 사진을 찍는다. 단, 구간 내에 특정 품종이 정확히 한 마리만 존재하는 "외톨이 사진"은 폐기처분한다. 폐기되는 사진의 총 개수를 구하라.
입력
첫 줄: N (소의 ...
6월 16일 01:00에 게시됨
LeetCode 2270: 누적합을 활용한 배열 분할 조건 탐색
문제 이해LeetCode 2270번 Split Array Largest Sum과 유사한 조건으로, 배열을 두 부분으로 나누었을 때 왼쪽 구간의 합이 오른쪽 구간의 합 이상이 되는 분할 지점의 개수를 구하는 문제입니다.길이가 n인 배열 nums에서 인덱스 i (0 ≤ i < n-1)를 기준으로 분할할 때, 다음 조건을 만족하면 유효한 분할입니다:sum(nums[0..i]) ≥ sum(nums[i+1..n-1])핵심 관찰전체 ...
6월 6일 21:21에 게시됨
트래킹 세그먼트 (이분 탐색, 구간 누적합)
문제 설명
n개의 0으로 초기화된 배열 a가 주어집니다. 또한 m개의 구간이 주어지며, 각 구간은 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 정의됩니다. 이는 배열 a의 부분 배열 a[l_i], a[l_i+1], ..., a[r_i]를 의미합니다.
특정 구간에서 1의 개수가 0의 개수보다 크다면 해당 구간을 아름다운 구간이라고 합니다. 예를 들어, a = [1, 0, 1, 0, 1]인 경우 구간 [1, 5]는 1이 3 ...
5월 31일 13:04에 게시됨
코드포스 대회 문제 풀이: B, C번 풀이 모음
최근 진행된 Codeforces 대회들의 주요 문제 풀이를 모아서 정리했습니다. 각 문제는 배열 처리, 구간 합, 그리디 알고리즘 등의 기법을 활용하여 효율적으로 해결할 수 있습니다.
Educational Codeforces Round 132 (Div. 2) – B번
수열이 주어질 때 특정 구간에서 인접 원소 간 차이의 합을 구하는 문제입니다. 오른쪽으로 이동할 때 증가 폭과 감소 폭을 각각 별도로 ...
5월 22일 09:50에 게시됨