알고리즘은 맞지만, 시간/메모리 측면에서 비효율적입니다.

첫 두 줄을 다음과 같이 바꾸기만 해도 (제 컴퓨터의 Python 3.6에서 실행해봤을 때) 메모리가 1.5GB 이상 필요하고 결국 Python이 MemoryError를 뱉었습니다.

최악의 경우 O(2^N)개의 원소가 possible에 저장되기 때문입니다. 원소가 오름차순일 때 그렇습니다)

possible이 현재 (지금까지의 길이, 마지막 원소)를 담고 있는 것 같은데, 다음과 같이 크기 N 정도의 배열로 접근해보시기 바랍니다.

possible[i] = (i번째 원소를 맨 마지막 원소로 하면서 가장 긴 증가하는 부분 수열의 길이)

덕분에 해결하였습니다! 거의 1시간 가까이 고민했던 것 같은데 정말 감사합니다!

알고리즘 문제 요즘 공부하기 시작한 학생인데 DP 문제가 많이 익숙하지 않네요!ㅠㅠ

메모리와 시간 사이에서 어떤 값을 저장해야 메모리를 효과적으로 사용할 수 있을지,

for문을 최소한으로 사용할지가 아직 익숙하지 않은 것 같습니다ㅠ

앞으로 DP 문제를 풀 때 메모리 역시 최악의 케이스를 고려하도록 해야겠네요.

정말 감사합니다!!