코드를 올려 주셔야 볼 수 있습니다.
7476번 - 최대 공통 증가 수열
반례 감사합니다
고민해봤는데 제 방식이 기존 LIS문제처럼 dp[n]값을 바탕으로 dp[n+1]을 추리하는 형태인데, 이 부분에서 문제가 생겼네요
제가 만든 로직은 '부분최적값이 전체최적값에 귀결된다' 는 식의 오류에 빠진듯 합니다.
이 생각을 바탕으로 좀더 쉬운 반례를 구해봤습니다 저랑 비슷한 오류에 빠지신 분들께 도움이 되었으면 좋겠네요
14
1 2 3 4 6 5 4 1 2 3 4 6 5 4
14
5 1 4 3 6 2 4 5 1 4 3 6 2 4
<위의 로직 답>
4
1 2 3 4
<정답>
5
1 3 4 5 6
처음부터 다시 풀어봐야겠네요 ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
coke 6년 전
구글링해서 관련 예제 다 넣어봤는데 어디가 틀렸는지 알 수가 없네요
4~5%에서 계속 틀렸습니다가 뜹니다
접근은 첫번째 배열을 기준으로 O(n^2) LIS를 구하는 for문에서 두번째 수열을 정렬후 lowerbound를 통해 가장 오른쪽에 오는 수들을 비교해서 공통증가수열인지 판별했습니다
코드 올려보았습니다