Floyd 알고리즘을 활용한 점진적 도로 재건 문제 해결
문제 개요
N개의 마을이 있고, 각 마을은 재건 완료 시간 t[i]를 가집니다. 마을 간 도로는 양방향이며 가중치 w를 갖습니다.
Q개의 쿼리 (u, v, T)가 주어질 때, 시간 T까지 재건된 마을만 통행 가능할 때 u에서 v까지의 최단 거리를 구해야 합니다.
데이터는 T가 비내림차순으로 주어집니다.
잘못된 접근: 다익스트라 + 시간 기반 그래프 추가
처음 생각한 방법은 ...
6월 22일 16:52에 게시됨
로그우 P1983 역급수 결정 (위상 정렬 활용)
문제 링크
https://www.luogu.org/problemnew/show/P1983
문제 설명
단방향 철도 노선 위에 1부터 n까지 번호가 매겨진 역이 있다. 각 역은 최소 1등급 이상의 등급을 가진다. 여러 대의 기차가 이 노선을 운행하며, 각 기차는 다음과 같은 조건을 만족한다: 만약 기차가 역 x를 정류한다면, 출발지와 도착지 사이에 등급이 역 x 이상인 모든 역은 반드시 정류해야 한다. ...
6월 18일 16:56에 게시됨
중산 집중 훈련 기록 (7.28–8.11)
7월 29일
주로 모의고사 중심으로 진행되었으며, 일부 문제에 대한 분석과 후기 포함.
T1
간단한 시뮬레이션 문제. CSP-S2023 T3보다도 쉬웠다. 디버그 문구를 지우지 않아서 실수했지만, 다행히 오답은 아니었다. 복잡도가 높을 수 있다는 점을 인지하고, 더 효율적인 접근 방식을 고려해야 한다. 결국 코드는 통과했으나, 조건이 애매하면 예외 처리가 필요하다.
T2
초기 ...
6월 11일 20:47에 게시됨
AtCoder Beginner Contest 399 풀이
A - Hamming Distance
문제 설명
두 문자열 S와 T가 주어졌을 때, 서로 다른 문자의 개수를 구한다.
풀이 방법
문자열을 순회하며 각 위치의 문자가 다를 때마다 카운트를 증가시킨다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s, t;
...
5월 25일 08:20에 게시됨