one Book a Day

그 전단계에 비해 실제 LIS 리스트 까지 뽑아내야 하는 문제이다. 전 문제는 LIS길이만을 측정하기에 배열 순서 상관없이 이분탐색으로 자기위치에 삽입, 계속 LIS배열을 초기화 새롭게 덮어씌우는 방법으로 길이를 측정했지만 이번문제는 temp배열에 삽입되는 모든 인자를 인덱스값과 인자를 묶어 전부 삽입해준 후 재검사를 통해 queue에 들어간 배열과 temp에 들어간 인덱스값을 비교해 동일하면 temp에서 그 값을 ans에 넣어주는 방식이다. 즉 이분탐색으로queue에서 index값을 관리하고 temp에서 그 값에 일치하는 x값들을 모두 관리하는 방식. import sys from bisect import bisect_left input = sys.stdin.readline n=int(input()) a..

처음에 조합으로짰다가 최대한 줄여도 메모리 시간초과나서 고생하다 결국 c++코드보고 이분탐색풀이로 다시 짰다. 이분탐색 안그래도 공부하려고 생각중이었는데 오늘 기본문제부터 조금씩 풀어봐야 할듯 싶다. 위는 조합풀이, 아래는 이분탐색 풀이. import sys input= sys.stdin.readline from itertools import combinations # N-1개의 사이에서 M-1개의 작대기를 뽑는 조합. # 각 max값중 최댓값과 slice한 작대기 위치 패킹해 저장. # 저장된 max값 정렬 후 맨앞에있는 배열 출력. N,M = map(int,input().split()) ball_lists = list(map(int,input().split())) maxes = float('inf')..