파이썬 알고리즘 074 | 최대 선 연결하기

74. 최대 선 연결하기

왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다.
왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다.
오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선
을 연결할 수 있는 지 구하는 프로그램을 작성하세요

▣ 입력설명
첫 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 1부터 N까지의 자연수 N개의 오른쪽 번호 정보가 주어집니다. 순서는 위쪽번호
부터 아래쪽번호 순으로입니다.
▣ 출력설명
첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다.
▣ 입력예제 1
10
4 1 2 3 9 7 5 6 10 8
▣ 출력예제 1
6

<내 풀이>

아..거의 다 온 것 같은데 한 부분에서 계속 막힌다, 아니면 아예 접근방법이 틀린건가?
==>문제를 잘못 이해하고 있었음..

n=int(input())
a=list(map(int, input().split()))
a.insert(0,0)

dy=[0]*(n+1)
cnt=0
for i in range(1,n+1) :
    if a.index(i)>i :
        dy[i]=1
        for j in range(1,a.index(i)) :
            #=>이 부분부터 사고가 꼬이기 시작한다
#print(max(dy)

<풀이>

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)

<반성점>

• 문제를 제대로 읽지 않아서 선이 \ 모양으로만 이어져야 한다는 걸로 이해하고 문제를 풀었었다 바보.. 문제를 제발 제대로 파악하자
• 이러한 조건이 그러므로 없다면 앞의 문제와 동일하게 풀어주면 됨

<배운 점>

• 최대 증가수열의 문제와 똑같은 맥락임
• 응용해서 다 연결해놓고, 최소 몇개의 선을 제거해야 교차하지 않는 선을 최대로 구할 수 있는가 ?할 수도 있음
• 혹은 다리 만들 때 같은 번호로 연결되어야 한다 할 때 만들 수 있는 최대다리개수를 물어볼 수도 있음

<2차 내 풀이>

n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
for i in range(2,n+1) :
    maxi=-1
    for j in range(i) : 
        if a[j]<a[i] and dy[j]>maxi :
            maxi=dy[j]
        dy[i]=maxi+1
print(max(dy))