[Algorithm] 2352.py 1365.py 파이썬

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))

LIS(Longest Increasing Subsequence) 알고리즘이라고 한다. 솔직히 읽어도 모르겠다.

문제를 보면서 천천히 하나씩 이어가보자.

1 -> 4 2 -> 2 연결선이 4 꼬이기 때문에 1 -> 4는 연결이 안된다.
3 -> 6 4 -> 3 연결선이 꼬이기 때문에 3 -> 6은 연결이 안된다.
5 -> 1 6-> 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))

똑같은 LIS(Longest Increasing Subsequence) 알고리즘 문제이다.