coding_test/BAEKJOON
백준 14003번 C++ 풀이
문제https://www.acmicpc.net/problem/14003시간 제한메모리 제한solved.ac 티어3초512MB플래티넘 5풀이 밀린 문제는 아니고 오늘 푼 문제이다. 문제 이름이 LIS니까 이 문제도 LIS이다. 다만, LIS를 역추적하는 문제이다. 2568번 문제를 설명하는 이전 글에서 간략하게 설명했고, 알만한 사람들은 알겠지만, LIS알고리즘은 LIS 자체를 구하는 것이 아닌 LIS의 길이를 구하는 알고리즘이다. 그렇기 때문에 dp 배열을 하나 더 선언하여, 해당 dp 테이블을 역순회하면서 LIS를 다시 찾아가는 방식을 사용한다.코드#include #define ALL(X) X.begin(), X.end()using namespace std;int n;vector arr;void in..
