nahwasa   4년 전

  1. 문제제목이 LCS라서 처음엔 LCS 알고리즘으로 풀었습니다. -> 답이야 나오겠지만 당연히 메모리초과
  2. 어차피 N x N 배열이 필요없으므로 배열크기를 2줄로 줄여서 풀었습니다. -> 답이야 나오겠지만 당연히 시간초과
  3. 줄일부분이 안보여서 여기에 힌트를 달라고 했습니다. (  https://www.acmicpc.net/board/view/38295 )
  4. @jh05013님의 힌트를 보고 LIS쪽으로 가닥을 잡고 (어차피 LCS로는 시간초과 처리가 안될것같으니) 시도를 해보다보니
  5. 통과됬습니다..

문제는 힌트에서 힌트를 얻어 LIS에 넣을것들을 바꾸다보니 된거라 -_-;;
(처음엔 A 입력에 해당하는 인덱스에 B를 넣어도 봤구요. -> 즉 A를 기준으로 B를 오름차순정렬)

결국엔 A를 입력받고, B에서 A와 동일한 값에 해당하는 인덱스를 순서대로 배열에 넣어 LIS를 진행하는게 답이었습니다.

음.. 제가 머리가 나쁜건 맞긴한데..
문제는 대강 머리로는 음 그래 1~N까지 모든 수가 있는거니까 대강 그렇게 되겠지!
싶기도 하면서도 명확하게 이게 왜 가능한지 잘 모르겠습니다.
맞는데 왜 맞은거죠?!

이제 풀었으니 풀이도 찾아봤지만 이 부분에 대해서는 그냥 당연한것처럼 넘어가시더라구요..
흐흑.. 알려주세요 ㅠ

sait2000   4년 전

음... 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

nahwasa   4년 전

아!!

어차피 1~N까지 양쪽 다 동일하게 있으니까, 양쪽다 같은 값에 대해 다른 값을 붙여도 상관없는거군요!!

와.. 완벽한 설명 감사드립니다 ㅠㅠ

6f363a77-e480-42b9-aff8-c98cd99fb667

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