백준 2631번 - 줄세우기

줄세우기 문제 바로 가기

풀이 날짜: 2026-01-19

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
students = []
for _ in range(n):
    students.append(int(input()))
dp = [1]*n

for i in range(n):
    for j in range(i):
        if students[i] > students[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))

print(count)

문제 핵심 요약:

이 문제의 목표는 학생들을 번호가 증가하는 순서로 만들기 위해 최소 몇 명을 옮겨야 하는지 구하는 것이다. 여기서 중요한 관찰은 “옮기지 않고 그대로 둘 수 있는 학생들의 최대 집합”을 찾으면, 나머지만 적절한 위치로 옮겨 전체를 증가 순으로 만들 수 있다는 점이다. 즉, 최대로 유지 가능한 증가 부분 수열의 길이(LIS) 를 구하면, 정답은 전체 n - LIS 길이가 된다.

LIS로 바꿔 생각하기

학생 번호 배열에서 최장 증가 부분 수열(LIS) 은 “이미 올바른 상대적 순서를 유지하고 있는 학생들”을 의미한다. 이 학생들은 자리 이동 없이 그대로 두어도 증가 순서를 유지할 수 있다. 따라서 LIS에 포함되지 않은 학생들만 이동시키면 전체가 증가 순이 될 수 있으므로, 최소 이동 인원은 자연스럽게 n - LIS가 된다. 이 문제는 결국 “LIS 길이만 구하면 된다”로 환원된다.

DP 정의

dp[i] = i번째 학생(students[i])을 마지막 원소로 하는 증가 부분 수열의 최대 길이

처음에는 어떤 학생이든 자기 자신만으로 길이 1짜리 증가 수열을 만들 수 있기 때문에 dp = [1] * n으로 시작한다.
이후 i를 끝으로 만들 수 있는 죄장 길이를 앞의 원소들과 비교하며 갱신했다.

헷갈렸던 것 정리

LIS 핵심

LIS 문제에서 가장 헷갈리는 부분은 dp[i] = max(dp[i], dp[j] + 1)이다.
이 식을 이해하기 위해 먼저 dp[i]가 무엇을 의미하는지 이해해야 한다. dp[i]는 단순히 “i번째까지의 LIS 길이”가 아니라, “i번째 원소를 반드시 마지막으로 사용하는 증가 부분 수열의 최대 길이” 를 의미한다. 즉, i번째 학생을 수열의 끝에 두었을 때, 가장 길게 만들 수 있는 경우를 저장하는 값이다.

i번째 학생을 끝에 둔다는 의미

i번째 학생을 수열의 마지막에 두려면, 그 앞에 오는 학생의 번호는 반드시 더 작아야 한다. 따라서 i번째 학생 앞에는 오직 j < i 이면서 students[j] < students[i] 인 경우만 올 수 있다. 이 조건이 코드에서 if students[i] > students[j] 로 표현된다.

Vienna sausage