11055번 - 가장 큰 증가하는 부분 수열
이 코드에서 어떻게 dp를 써야할지 모르겠습니다.
아예 다시 코드를 짜야하는 걸까요 ?
10
1 100 2 50 60 3 45 6 7 8
답: 113
5
1 100 3 4 101
답: 202
7
3 2 1 2 3 4 5
답: 15
은 나오는데, 시간초과나 나옵니다.
이렇게 재귀를 짜면 1,2,3,4 ...1000까지의 수열일 때는 거의 O(!1000) 아닐까요?? 이거 인터넷에 lis찾으시면 dp로 쉽게 N^2에 푸는 방식이 있습니다.
댓글을 작성하려면 로그인해야 합니다.
tmvld9 5년 전
이 코드에서 어떻게 dp를 써야할지 모르겠습니다.
아예 다시 코드를 짜야하는 걸까요 ?
10
1 100 2 50 60 3 45 6 7 8
답: 113
5
1 100 3 4 101
답: 202
7
3 2 1 2 3 4 5
답: 15
은 나오는데, 시간초과나 나옵니다.