2018 창사이공대학 제13회 프로그래밍 경진대회 문제 풀이
A. LL
문제 설명: 입력된 문자열이 대소문자 구분 없이 "lovelive"와 정확히 일치하는지 판별하는 문제입니다. 문자열 길이는 최대 100이며, 입력은 최대 100개의 그룹으로 제공됩니다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string input;
while (getline(cin, input)) {
t ...
7월 11일 23:10에 게시됨
차분 제약 시스템: 그래프 이론으로 푸는 부등식 문제
여러 개의 선형 부등식으로 표현된 제약 조건 하에서 각 변수의 최댓값이나 최솟값을 구해야 할 때, 그래프 이론의 최단경로/최장경로 알고리즘을 활용할 수 있다. 이를 차분 제약 시스템(Difference Constraints System)이라 한다.
핵심 원리: 부등식의 방향성
부등식 xi ≤ xj + ck는 정점 j에서 정점 i로 가는 가중치 ck의 유향 간선으로 해석한다.
목표그래프 해석 ...
7월 11일 02:13에 게시됨
Floyd 알고리즘을 활용한 점진적 도로 재건 문제 해결
문제 개요
N개의 마을이 있고, 각 마을은 재건 완료 시간 t[i]를 가집니다. 마을 간 도로는 양방향이며 가중치 w를 갖습니다.
Q개의 쿼리 (u, v, T)가 주어질 때, 시간 T까지 재건된 마을만 통행 가능할 때 u에서 v까지의 최단 거리를 구해야 합니다.
데이터는 T가 비내림차순으로 주어집니다.
잘못된 접근: 다익스트라 + 시간 기반 그래프 추가
처음 생각한 방법은 ...
6월 22일 16:52에 게시됨