[백준: Python] 14002 - 가장 긴 증가하는 부분 수열 4

[문제]

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

기본적으로 LIS 문제에 수열을 이루는 값을 기록하는 조건이 추가된 문제입니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.arr = list(map(int, input().split()))
        self.answer = []

---

[풀이]

    def solve(self):
        dp = [1] * self.n
        prev = [-1] * self.n  # 이전 인덱스 추적을 위한 배열

        max_length = 0
        max_index = 0

        for i in range(1, self.n):  # dp 계산 및 prev 배열 채우기
            for j in range(i):
                if self.arr[i] > self.arr[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j  # 이전 인덱스 기록

            if dp[i] > max_length:  # 최대 길이와 그 위치 업데이트
                max_length = dp[i]
                max_index = i

        while max_index != -1:  # 역추적
            self.answer.append(self.arr[max_index])
            max_index = prev[max_index]

        self.answer.reverse()  # 역추적이므로 리스트를 뒤집어야 올바른 순서가 됨

        print(len(self.answer))
        print(*self.answer)

수열의 길이를 기록할 리스트와 그 값들을 찾아낼 리스트를 선언합니다.

1. 기준값(i)과 비교하며 값이 증가하는 부분을 찾아냅니다.
   1. 증가하는 시점이므로 기준값에 증가가 발생하는 시점(j)의 값 + 1로 갱신합니다.
   2. 기준값이 어느 값에서 이어지는지 prev 리스트에 기록합니다.
2. 기준값과 비교가 끝났다면 최대 길이를 갱신합니다.
   1. max_index는 추후 가장 긴 리스트의 값을 추적할 때 시작하는 인덱스가 됩니다.
3. 모든 탐색이 끝나고 수열이 만들어졌다면, 가장 긴 수열의 마지막 값부터 역으로 값을 추적해 나갑니다.
4. 값을 역추적했으므로, 출력 기준에 맞추기 위해 뒤집습니다.
5. 문제 출력 조건에 맞춰 값을 출력합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n = int(input())
        self.arr = list(map(int, input().split()))
        self.answer = []

    def solve(self):
        dp = [1] * self.n
        prev = [-1] * self.n  # 이전 인덱스 추적을 위한 배열

        max_length = 0
        max_index = 0

        for i in range(1, self.n):  # dp 계산 및 prev 배열 채우기
            for j in range(i):
                if self.arr[i] > self.arr[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j  # 이전 인덱스 기록

            if dp[i] > max_length:  # 최대 길이와 그 위치 업데이트
                max_length = dp[i]
                max_index = i

        while max_index != -1:  # 역추적
            self.answer.append(self.arr[max_index])
            max_index = prev[max_index]

        self.answer.reverse()  # 역추적이므로 리스트를 뒤집어야 올바른 순서가 됨

        print(len(self.answer))
        print(*self.answer)


problem = Main()
problem.solve()

삼성 기출부터 시작해서 역추적 테크닉이 종종 쓰이는 거 같습니다. 현재 시점에 이전 시점을 기록하는 방법으로 어렵지 않으니, 익혀두면 요긴하게 쓰일 것으로 생각됩니다.

---