adfsfsf   2년 전

1. 각 위치마다, 가능한 증가하는 부분수열의 길이를 구합니다.

2. 역순으로, 가능한 감소하는 부분수열의 길이를 구합니다.

3. 그 합이 가장 큰 경우를 출력합니다.

그런데 이 방법을 사용하려면 기존의 방법으로는 좀 힘듭니다. 왜냐하면, 기존에는 한 방향만 구하면 되었고, 최종 결과만 알면 되었기 때문에 가장 긴 부분수열 하나만을 구하는 방식을 사용했기 때문입니다. 하지만 이 방식을 쓰려면, 모든 수에 대해서, 차근차근 구해나가야 합니다.

저는 이 문제를 해결하기 위해 우선순위 큐를 직접 만들어서 풀었습니다. 더 쉬운 방법이 있을 수도 있겠지만, 어느 방법이 되든, 양방향을 다 구하기 위해서는 모든 위치에 대해 값을 구해야 합니다. 이 점을 생각하시면서 풀어보세요.

adfsfsf   2년 전

저는 C언어를 사용했기에 우선순위 큐를 구현한 겁니다. 다른 언어들은 이미 구현된 경우가 많으니 비교함수만 잘 만드시면 될 거에요.

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