11053번 - 가장 긴 증가하는 부분 수열
문제를 잘 읽어보시면 출력은 '가장 긴 증가하는 부분 수열의 길이' 이지, '증가하는 부분 수열' 그 자체가 아닙니다.
질문 게시판에 올라오는 많은 종류의 질문들이 "이렇게 풀었는데, 이게 맞나요?" 식의 질문인 것도 이와 조금은 관련이 있는 것 같습니다.
그래서 이 문제가 일반적인 dp 방식 풀이 + 이분 탐색을 적용시킬 수 있는 것이기도 합니다. 만약 실제로 증가하는 부분 수열을 구하고자 한다면, 이전까지의 증가하는 부분 수열이 최대 길이가 될 때마다, 다른 배열에 업데이트하는 방식으로도 구현할 수 있을 것입니다.
추천문제: https://www.acmicpc.net/proble...
댓글을 작성하려면 로그인해야 합니다.
peydihalta 4년 전 1
문제를 잘 읽어보시면 출력은 '가장 긴 증가하는 부분 수열의 길이' 이지, '증가하는 부분 수열' 그 자체가 아닙니다.
질문 게시판에 올라오는 많은 종류의 질문들이 "이렇게 풀었는데, 이게 맞나요?" 식의 질문인 것도 이와 조금은 관련이 있는 것 같습니다.
그래서 이 문제가 일반적인 dp 방식 풀이 + 이분 탐색을 적용시킬 수 있는 것이기도 합니다. 만약 실제로 증가하는 부분 수열을 구하고자 한다면, 이전까지의 증가하는 부분 수열이 최대 길이가 될 때마다, 다른 배열에 업데이트하는 방식으로도 구현할 수 있을 것입니다.