2631. [Python]줄세우기

1. 문제

 

https://www.acmicpc.net/problem/2631

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• LIS(DP) 알고리즘

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

N = int(input())

num_list = []
# 숫자 리스트 추가
for _ in range(N):
    num_list.append(int(input()))
# LIS 알고리즘 적용할 리스트
long_length = [0] * N
# LIS 알고리즘
for i in range(N):
    # i 번 값 1로 초기화
    long_length[i] = 1
    # 0번 인덱스부터 i 번 인덱스까지 반복문진행
    for j in range(0,i):
        # i 번 인덱스 값보다 작은경우
        if num_list[j] < num_list[i]:
            # 현재 i 인덱스에 기존의 i 인덱스 값 혹은 값이 작은 j 번 인덱스 +1 한 값중 맥스값 추가
            long_length[i] = max(long_length[i], long_length[j]+1)
# 개수 N 에서 LIS 적용한 max 값 빼줌
print(N-max(long_length))

 

4. 문제를 풀고난 후 생각

 

• DP 문제인 것은 알고있었으나 LIS 라는 명칭의 알고리즘이라는 것은 몰랐다.
• 최장 증가하는 연속 수열만 찾게되면 그 수열은 유지한채 나머지 수열의 위치만 바꿔주면 되기 때문에 최장 길이 수열을 찾아낸 후 전체 수의 개수 N 에서 빼기를 해주면 된다.
• LIS 알고리즘에 관해서 정리를 한번 진행한 후 다른 문제도 접해볼 예정이다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• LIS 알고리즘
• DP