반응형
백준11568번
-
[백준 11568번] 민균이의 계략 Java 풀이문제풀이/백준 2021. 10. 6. 21:42
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어보았습니다. 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열과 문제는 동일 합니다. 그러나 일전의 문제의 경우 DP[N]을 구하기 위하여 1부터 N-1까지 반복하여 정답을 구하는 방식으로 구현하였습니다. 이 방법은 최종 길이인N을 구하기 위해서는 worst-case인 N * (N-1)번 반복을 수행하므로 시간 복잡도가 O(N2)이 됩니다. 만약 이번 문제 또한 일전의 방식으로 풀이 시 시간초과가 되게 됩니다. 하여 Lower Bound를 이용하여 시간복잡도가 O(nlogn)인..