문제 링크 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 저번에 풀이를 올렸던 LIS 2번 문제를 응용해서 풀 수 있는 문제입니다! 열심히 풀어봅시다~ 풀이 LIS(DP+이분탐색)을 내림차순으로 풀이하면 됩니다. 내림차순으로 풀이 후에, 열외할 병사를 출력하기 위해 내림차순으로 저장한 배열(seq)의 크기를 n에서 빼주었습니다. 전에 썼던 LIS 2번 문제 와 흐름이 거의 동일하니, 자세한 풀이는 링크를 참고해주세요! 풀이코드 #include using namespace std; #de..
LIS
문제 링크 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 어제 풀어봤던 11053번: 가장 긴 증가하는 부분 수열 문제에 이어서 2번째 문제입니다. 이전 문제는 \(O(N^2)\) 의 시간복잡도로 풀 수 있었지만, 이번 문제부터는 \(O(N \log N)\) 의 시간복잡도로 해결해야합니다! 차근차근 해결방법을 설명하며 풀이해보겠습니다. 풀이 LIS문제를 DP+이분탐색으로 풀이하면 됩니다. 이 문제에서는 이전 문제와는 다르게, N의 범위가 100만까지로 무지막지하게 큽니다. N의 크기가 크기 때문에, \(O(N..
문제 링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 오랜만에 DP 문제를 들고 왔습니다! 이 문제는 그 이름도 유명한 가장 긴(최장) 증가 부분 수열 (LIS: Longest Increasing Subsequence) 입니다. 이 문제는 시리즈(1번부터 5번)가 있으며, 나무위키에 등재되어 있을 정도로 잘 알려져 있습니다. 문제를 차근차근 살펴보며 풀이해봅시다! 풀이 DP를 이중선형시간(\(O(N^2)\))으로 메모라이즈하며 ..
