[BOJ]2631(python)

백준 2631(줄세우기) python 풀이입니다

전체 부분에서 최장증가 길이를 빼면 되기 때문에
LIS를 이용해서 풀면 된다

LIS(최장 증가 수열)

한 수열에서 숫자가 증가하는 최대 길이를 찾는 것으로
이분탐색 혹은 DP를 이용해서 풀 수 있는데 이번에는 DP를 이용해서 풀었다

메모이제이션 부분에는 현재까지 몇개의 숫자만큼 증가했는지를 넣으면 된다
처음에는 1로 초기화해준다(증가한 횟수는 나자신 한번 뿐)

만일 현재의 값이 이전 값보다 크다면,
이전의 증가 횟수와 현재의 증가횟수를 비교해서 값을 갱신하면 된다
(현재의 증가 횟수 vs 이전의 증가 횟수 + 1)

코드

from collections import defaultdict

def solution():
    N = int(input())
    C = []

    for _ in range(N):
        C.append(int(input()))
    
    memo = defaultdict(lambda : 1)

    for i in range(N):
        for j in range(i):
            if C[i] > C[j]:
                if memo[i] < memo[j] + 1:
                    memo[i] = memo[j] + 1

    print(N - max(memo.values()))
    

solution()

1. 값을 받고 memo(증가 횟수)를 1로 갱신해준다
2. 배열 값을 모두 돌면서 현재 값과 다음을 비교한다
   • 이전의 값과 비교해서 현재의 값이 크다면 비교를 한다
   • 이전의 증가 횟수와 현재의 증가횟수를 비교한다
     - 현재의 증가 횟수 < 이전의 증가 횟수 + 1 이라면 값을 갱신한다
3. 전체 갯수에서 가장 많이 증가한 횟수를 뺀다