13711번 - LCS 4
문제는 힌트에서 힌트를 얻어 LIS에 넣을것들을 바꾸다보니 된거라 -_-;;(처음엔 A 입력에 해당하는 인덱스에 B를 넣어도 봤구요. -> 즉 A를 기준으로 B를 오름차순정렬)
결국엔 A를 입력받고, B에서 A와 동일한 값에 해당하는 인덱스를 순서대로 배열에 넣어 LIS를 진행하는게 답이었습니다.
음.. 제가 머리가 나쁜건 맞긴한데..문제는 대강 머리로는 음 그래 1~N까지 모든 수가 있는거니까 대강 그렇게 되겠지!싶기도 하면서도 명확하게 이게 왜 가능한지 잘 모르겠습니다.맞는데 왜 맞은거죠?!
이제 풀었으니 풀이도 찾아봤지만 이 부분에 대해서는 그냥 당연한것처럼 넘어가시더라구요..흐흑.. 알려주세요 ㅠ
음... jh05013님이 주신 힌트대로 A가 1 2 3 4 5...면 B의 LIS 길이가 답이라는 건 이해하셨을거라고 생각하는데 그러면 그 다음은 말 그대로 값을 다시 붙이는 겁니다. 지금 B에 하시는 변환을 A를 복제한 다음 거기다도 똑같이 적용하면 0 1 2 3 4... 이런 식이 되니까요.
1 3 2 4 5
5 2 3 1 4
->
0 1 2 3 4
4 2 1 0 3
아!!
어차피 1~N까지 양쪽 다 동일하게 있으니까, 양쪽다 같은 값에 대해 다른 값을 붙여도 상관없는거군요!!
와.. 완벽한 설명 감사드립니다 ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
nahwasa 4년 전
문제는 힌트에서 힌트를 얻어 LIS에 넣을것들을 바꾸다보니 된거라 -_-;;
(처음엔 A 입력에 해당하는 인덱스에 B를 넣어도 봤구요. -> 즉 A를 기준으로 B를 오름차순정렬)
결국엔 A를 입력받고, B에서 A와 동일한 값에 해당하는 인덱스를 순서대로 배열에 넣어 LIS를 진행하는게 답이었습니다.
음.. 제가 머리가 나쁜건 맞긴한데..
문제는 대강 머리로는 음 그래 1~N까지 모든 수가 있는거니까 대강 그렇게 되겠지!
싶기도 하면서도 명확하게 이게 왜 가능한지 잘 모르겠습니다.
맞는데 왜 맞은거죠?!
이제 풀었으니 풀이도 찾아봤지만 이 부분에 대해서는 그냥 당연한것처럼 넘어가시더라구요..
흐흑.. 알려주세요 ㅠ