최대 선 연결하기
왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다.
왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다.
오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선
을 연결할 수 있는 지 구하는 프로그램을 작성하세요.
위의 그림은 오른쪽 번호 정보가 4 1 2 3 9 7 5 6 10 8 로 입력되었을 때 선이 서로 겹치지
않고 연결할 수 있는 최대 선을 개수 6을 구한 경우입니다.
▣ 입력설명
첫 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 1부터 N까지의 자연수 N개의 오른쪽 번호 정보가 주어집니다. 순서는 위쪽번호
부터 아래쪽번호 순으로입니다.
▣ 출력설명
첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다.
▣ 입력예제 1
10
4 1 2 3 9 7 5 6 10 8
▣ 출력예제 1
6
문제풀이
import sys
sys.stdin=open("input.txt", "r")
n = int(input())
arr2=list(map(int, input().split()))
arr2.insert(0,0)
print(arr2)
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 arr2[j]<arr2[i] and dy[j]>max:
max=dy[j]
dy[i]=max+1
if dy[i]>res:
res=dy[i]
print(res)
최대부분 증가수열을 구하면 다음과 같다.
▶ arr[ i ]의 의미 : 내가 만들고자 하는 증가수열의 마지막항
▶ dy[ j ]의 의미 : arr[ j ]가 마지막항인 증가수열의 최대 길이
▶ dy[ i ]=max+1 의미 : 증가수열의 가장 큰 길이(max)에
마지막항 arr2[ i ]가 한 개가 붙으므로 dy[i]=max +1
▶ dy[ i ]의 의미 : arr[ i ]가 마지막항인 증가수열의 최대 길이
▶ i는 마지막에 있는 항을 의미한다.
▶ if 조건을 만족하지 않는다면 max+1 즉 max에 마지막항 arr[i] 1개가 붙어서
증가수열의 길이를 증가시킨다.
▶ for j in range(i-1, 0, -1) ← arr[i]보다 앞에 있는 요소를 scan하고 싶을 때★★
디버깅을 해보자
'파이썬 알고리즘 > 동적계획법' 카테고리의 다른 글
6. 가장 높은 탑 쌓기(LIS 응용) (0) | 2022.11.23 |
---|---|
4. 최대 부분 증가수열(LIS: Longest Increasing Subsequence) (0) | 2022.11.23 |
3. 돌다리 건너기(Bottom-Up) (0) | 2022.11.23 |
2.네트워크 선 자르기(Top-Down방식) (0) | 2022.11.23 |
1. 네트워크 선 자르기(Bottom-Up) (0) | 2022.11.23 |