테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Jump Jump Championship ======

===== 풀이 =====
  * [[ps:tutorial:lis#LIS 복원하기|가장 긴 증가하는 부분수열을 복원]]하는 기본적인 문제
  * 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1974. Jump Jump Championship".

- Problem link: https://www.acmicpc.net/problem/1974
- Solution link: http://www.teferi.net/ps/problems/boj/1974

Tags: [LIS]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.run_n_times
def main():
    _N = int(sys.stdin.readline())
    sizes = [int(x) for x in sys.stdin.readline().split()]

    lis_inds = seqtask.longest_inc_subseq_indexes(sizes)
    print(len(lis_inds))
    print(*(x + 1 for x in lis_inds))


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_inc_subseq_indexes|teflib.seqtask.longest_inc_subseq_indexes]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}