coke   6년 전

구글링해서 관련 예제 다 넣어봤는데 어디가 틀렸는지 알 수가 없네요

4~5%에서 계속 틀렸습니다가 뜹니다

접근은 첫번째 배열을 기준으로 O(n^2) LIS를 구하는 for문에서 두번째 수열을 정렬후 lowerbound를 통해 가장 오른쪽에 오는 수들을 비교해서 공통증가수열인지 판별했습니다

코드 올려보았습니다

jh05013   6년 전

코드를 올려 주셔야 볼 수 있습니다.

coke   6년 전

글 수정했습니다 ㅎㅎ 정리를 안해서 코드가 좀 조잡하네요

jh05013   6년 전

몇 시간 전에 "다른 사이트에 있던 풀이를 냈더니 틀린다"라고 썼는데, 그건 사이트가 틀린 거였습니다. 그 답변은 지웠습니다.

코드가 길고 자바는 잘 모르는 관계로 정확히 어디라고 짚어 드릴 수는 없으나... 반례를 일단 만들었습니다. 답은 8 (-10 -8 -5 -4 1 2 8 9)입니다. 그리고 두 수열의 맨 앞의 -10을 지우면 제대로 7이 나옵니다.

coke   6년 전

반례 감사합니다

고민해봤는데 제 방식이 기존 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

2 3 4


<정답>

5

1 3 4 5 6


처음부터 다시 풀어봐야겠네요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.