dusrlf13   1일 전

입력된 값을 array 리스트에 저장하고 첫번째 인덱스부터 모든 증가수열을 따져본 뒤 현재의 최댓값보다 해당 케이스의 길이가 길다면 갱신해주는 방식으로 코드를 짰는데 시간 초과가 나버리네요...

제 생각에 이 코드가 가지는 시간 복잡도는 N개의 입력중에서 N-1개의 남은 요소들을 검사하니 최대 O(N^2)라고 생각이 되는데 맞는지 궁금합니다.
또한 DP적 방법을 통해 문제를 해결하려면 어떻게 해야 할지 조언을 구하고 싶습니다 ㅠㅠ


반례는 거의 다 맞는 것 같습니다...

azberjibiou   1일 전

3중 for문이면 N^3 아닌가요?

댓글을 작성하려면 로그인해야 합니다.