루고 P15440 문제 해설
루고 문제에 대한 제 해법입니다.
문제의 핵심은 신호등의 수가 2025개라는 점에서 출발하며, 이때 시간 복잡도가 O(n^2)보다 작은 동적 계획법(DP)을 고려해야 합니다.
각 조작 후 불이 켜진 횟수와 초기 상태 간의 차이를 상태로 설정하면 편리합니다. 첫 번째 조작 후 상태는 0으로 시작합니다. 여기서 dp[i][j]는 (i+1)번째 조작 후 상태 j를 가질 경우의 수를 나타냅 ...
8월 3일 16:20에 게시됨
NOIP2018 Day2T2 填数游戏
이 문제는 n×m 격자에 0과 1을 채워넣는 방식의 수를 세는 조합 문제입니다. 핵심 조건은 오른쪽 우선 경로의 01 문자열이 아래쪽 우선 경로의 01 문자열보다 사전순으로 작거나 같아야 한다는 것입니다.
작은 케이스 분석과 패턴 발견
먼저 n ≤ 3인 경우를 완전탐색으로 해결할 수 있습니다. DFS를 통해 모든 가능한 배치를 검증하면 다음과 같은 결과를 얻습니다:
2 : ...
7월 23일 22:03에 게시됨
다이나믹 프로그래밍 문제 풀이 모음
목차
백준 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에 게시됨
2025년 광저우대학교 프로그래밍 경진대회 신입생 대회
A 마법 문 Trial
크기 비교 문제, 난이도 1성
#include <iostream>
using namespace std;
int main()
{
int x, y, z, w;
cin >> x >> y >> z >> w;
if (x < w && y == z)
cout << "YES";
else
cout << "NO";
return 0;
}
B 약초 채집사
약초를 수집 ...
6월 27일 06:21에 게시됨
선분 트리 병합을 이용한 [FJOI2018] 지도자 그룹 문제 해결
먼저 이 문제는 그리디로 풀기 어려우므로 동적 계획법(DP)을 고려할 수 있습니다.
처음에는 \(dp_{i, j}\)를 \(i\)번 노드를 루트로 할 때 선택된 노드 중 최소 가중치가 \(j\)인 최대 멤버 수로 정의하는 직관적인 방법이 있습니다. 하지만 이 방법은 \(O(n^3)\)의 시간 복잡도를 가집니다. 많은 전이 과정이 동일하므로 비효율적입니다. 더 빠른 전이를 위해 상태를 변 ...
6월 25일 01:53에 게시됨
:NOIP 시뮬레이션 경진대회 문제 풀이
T1 다채로운 색상
문제는 다음과 같습니다:
nxm 크기의 행렬이 주어집니다.
(i,j) 위치에는 색깔 ci,j가 있습니다.
네 모서리의 색상이 모두 동일하지 않은 모든 하위 행렬의 수를 구하세요.
시간 복잡도 O(n²m)으로 해결할 수 있습니다. 두 행을 선택한 뒤 열을 스캔하면서 해당 열의 값들이 같으면 답에 기여할 가능성이 있습니다. 이를 위해 카운트 배열을 ...
6월 17일 19:19에 게시됨
Codeforces Round #574 (Div. 2) 기술 블로그 및 문제 풀이
Problem A: Drinks Choosing
N명의 학생들이 각자 선호하는 음료 맛이 있습니다. 총 $\lceil n/2 \rceil$개의 세트가 제공되며, 각 세트에는 같은 맛의 음료 2병이 들어 있습니다. 목표는 최대한 많은 학생이 자신이 원하는 맛의 음료를 받을 수 있도록 배분하는 것입니다.
가장 효율적인 방법은 동일한 맛을 원하는 학생들을 2명씩 묶어 한 세트를 주는 것입니다. 이렇게 ...
6월 14일 17:30에 게시됨
중산 집중 훈련 기록 (7.28–8.11)
7월 29일
주로 모의고사 중심으로 진행되었으며, 일부 문제에 대한 분석과 후기 포함.
T1
간단한 시뮬레이션 문제. CSP-S2023 T3보다도 쉬웠다. 디버그 문구를 지우지 않아서 실수했지만, 다행히 오답은 아니었다. 복잡도가 높을 수 있다는 점을 인지하고, 더 효율적인 접근 방식을 고려해야 한다. 결국 코드는 통과했으나, 조건이 애매하면 예외 처리가 필요하다.
T2
초기 ...
6월 11일 20:47에 게시됨
문자열 편집 거리와 서브시퀀스 개수 구하기: 동적 계획법 완전 정복
이번 글에서는 문자열 처리를 위한 동적 계획법(DP)의 세 가지 핵심 문제를 살펴보겠습니다. 각 문제는 이전 문제의 개념을 확장하여 최종적으로 편집 거리(Edit Distance) 문제를 해결합니다.
1. 서로 다른 서브시퀀스 개수
문자열 s와 t가 주어졌을 때, s의 서브시퀀스 중 t와 동일한 것의 개수를 구합니다. 편집 거리 개념에서 '삭제'는 긴 문자열의 문자를 제거하는 ...
6월 6일 16:59에 게시됨
문제 해결을 위한 알고리즘 접근
A 문제
링크
연속된 두 개의 '달콤한' 요소가 있으면 나머지 요소들을 모두 먹을 수 없습니다.
코드 보기
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string dishes[105];
for (int i = 0; i < n; ++i) {
cin >> dishes[i];
if (i > 0 && ...
5월 28일 19:00에 게시됨