[문제] https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [문제 풀이] 수열을 구하는 부분을 가장 긴 증가하는 부분 수열4 에서 했던 방식으로는 (N^2)이 이루어지므로 해당 문제의 조건인 N (1 ≤ N ≤ 1,000,000) 를 만족시키지 못한다. 고로, 가장 긴 증가하는 부분 수열2 에서 했던 방식으로 만들 경우 시간복잡도가(N log N)이니 해당 방식을 이용해서 수열을 구하는 것이 이번 문제의 키 포인트다..
[C++][백준 14003] 가장 긴 증가하는 부분 수열 5
[문제] https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [문제 풀이] 수열을 구하는 부분을 가장 긴 증가하는 부분 수열4 에서 했던 방식으로는 (N^2)이 이루어지므로 해당 문제의 조건인 N (1 ≤ N ≤ 1,000,000) 를 만족시키지 못한다. 고로, 가장 긴 증가하는 부분 수열2 에서 했던 방식으로 만들 경우 시간복잡도가(N log N)이니 해당 방식을 이용해서 수열을 구하는 것이 이번 문제의 키 포인트다..
2022.09.12