Lis2 [백준 7570번] 줄 세우기 n = int(input()) data = list(map(int,input().split())) data.insert(0,0) index_list = [0]*(n+1) count = 1 max_length = -1 for i in range(1,n+1): index_list[data[i]] = i for i in range(1,n): if index_list[i] < index_list[i+1]: count += 1 max_length = max(max_length, count) else: count = 1 if max_length != -1: print(n - max_length) else: print(0) 이번 문제는 임의의 순서로 세워진 번호를 맨 앞이나 맨 뒤로만 이동시킬 수 있다는 가정 하에 .. 2023. 8. 14. [백준 2631번] 줄세우기 n = int(input()) data = [] dp = [1]*n for i in range(n): data.append(int(input())) for i in range(n): for j in range(i): if data[i] > data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 임의의 순서로 세워진 번호를 번호 순서대로 배치하기 위한 최소한의 이동횟수를 구하는 문제이다. 번호를 옮기는 횟수를 최소화하기 위해서는 번호 순서대로 세워져있는 어린이들을 최대한 많이 고정시키고 나머지만 이동시켜야 한다. 즉, 가장 긴 증가하는 부분수열 LIS(Longest Increasing Subsequence)의 길이를 구하고 이를 전체 어린이 수에서 빼.. 2023. 8. 14. 이전 1 다음
