Algorithm - 최대 선 연결하기(LIS 응용)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[최대 선 연결하기(LIS 응용)]

 

왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 한다.

왼쪽 번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있다.

오른쪽의 번호 정보가 위에서부터 아래로 주어질 때, 선이 서로 겹치지 않고 최대 몇 개의 선을 연결할 수 있을지 구하는 프로그램을 작성하시오.

 

예시

 

위의 그림은 오른쪽 번호 정보가 4, 1, 2, 3, 9, 7, 5, 6, 10, 8로 입력되어 있을 때, 선이 서로 겹치지 않고 연결할 수 있는 선의 최대 값(6개)을 구한 경우이다. 

 

 

*입력 설명

첫 번째 줄에는 자연수 N(1 ≤ N ≤ 100)이 주어진다.

두 번째 줄부터 1부터 N까지 자연수 N개의 오른쪽 번호 정보가 주어진다.

단, 순서는 위쪽번호부터 아래쪽번호 순이다.

 

*출력 설명

첫 번째 줄에 겹치지 않고 그을 수 있는 선의 최대 개수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_77.txt', 'rt')

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
dy = [0] * (n+1)
dy[1] = 1
res = 0

for i in range(2, n+1):
    max = 0
    for j in range(i-1, 0, -1):
        if arr[j] < arr[i] and dy[j] > max:
            max = dy[j]
    dy[i] = max + 1
    if dy[i] > res:
        res = dy[i]
        
print(res)

# 출력 : 6

 

input_77.txt(입력)

10
4 1 2 3 9 7 5 6 10 8

 

 

중요내용

1. 해당 문제는 최대 부분 증가수열 문제와 원리가 동일하다. (문제의 구조만 변경되었음)
2. 이 문제에서도 오른쪽 번호 정보의 순서가 변경되면 안된다.
3. 답안의 코드는 최대 부분 증가수열의 문제와 동일하지만, 문제의 구조을 보고 LIS의 개념을 활용하여 답안을 도출하는 접근법이 중요하다.