[Algorithm] 2352.py 1365.py pi sun

2352 py半導体設計

from bisect import bisect
n=int(input())
data=list(map(int,input().split()))

# 연결선 이을 수 있으면 
dp=[data[0]]
for i in range (1,n):
    # 연결선을 꼬인게 없는지 판단
    # 가능한 연결선 중 가장 큰 값과 비교
    if data[i]>dp[-1]:
        # 크면 집어넣음
        dp.append(data[i])
    else:
        # 작으면 그 값이 들어갈 수 잇는 index를 찾아서 그 인덱스를 교체 
        dp[bisect(dp,data[i])]=data[i]
print(len(dp))

LongestIncreating Subsequence(LIS)アルゴリズムと呼ばれます.正直読んでもわかりませんが

問題を見てゆっくりと次から次へと.

1->4-2->2接続線に4本の撚り線があるため、1->4は接続できません.
3->6->3接続線がねじれているため、3->6は接続できません.
5->16->5接続線がねじれているため、5->1は接続できません.
ここで見つけられるのは、以前の値に比べて小さいと接続線が歪むことです.
この考えを用いて,コードに移動した部分を注釈で説明した.
リファレンス
https://blog.naver.com/kellygirl4028/222447631561

1365.py

from bisect import bisect
n=int(input())
data=list(map(int,input().split()))

dp=[data[0]]
for i in range (1,n):
    if data[i]>dp[-1]:
        dp.append(data[i])
    else:
        dp[bisect(dp,data[i])]=data[i]

print(n-len(dp))

同様にLongest Increating Subsequence(LIS)アルゴリズムの問題である.