최장 증가 부분 수열의 응용 문제와 해결 전략
교차하지 않는 다리 건설 문제
강의 양안에 위치한 도시들을 연결하는 다리를 건설할 때 교차하지 않도록 최대 다리 수를 구하는 문제입니다. 하안 도시를 배열 인덱스로, 상안 도시 번호를 값으로 매핑하면 최장 증가 부분 수열(LIS) 문제로 변환됩니다. 도시 쌍을 정렬한 후 LIS 길이를 계산합니다.
#include <iostream>
#include <algorithm>
using namesp ...
7월 3일 03:26에 게시됨