9702번 - LIS
수열 S가 [1, 5, 2, 4, 3]일 때 풀이입니다.
저는 이 문제를 "연속적인 최장 증가 부분 수열" 이라고 해석해서 [1, 5, 2, 4]일 때, LIS의 길이가 2라고 해석했습니다. (5때문에 끊겨서 연속적이지 않으니까)
근데, 질문 게시판에 있는 테스트 케이스는 이렇게 해석했을 때와 결과가 동일해서 삽질을 했습니다... 1시간 동안 맞왜틀을 경험했습니다.
혹시 저같이 오해하신 분 계시면 도움이 되실거라 믿습니다..
입력
댓글을 작성하려면 로그인해야 합니다.
byungmeo 1년 전
수열 S가 [1, 5, 2, 4, 3]일 때 풀이입니다.
저는 이 문제를 "연속적인 최장 증가 부분 수열" 이라고 해석해서 [1, 5, 2, 4]일 때, LIS의 길이가 2라고 해석했습니다. (5때문에 끊겨서 연속적이지 않으니까)
근데, 질문 게시판에 있는 테스트 케이스는 이렇게 해석했을 때와 결과가 동일해서 삽질을 했습니다... 1시간 동안 맞왜틀을 경험했습니다.
혹시 저같이 오해하신 분 계시면 도움이 되실거라 믿습니다..
입력
5
1 5 2 4 3