알고리즘||코딩테스트/백준
[백준 2550번] 전구 - Python
째로스
2023. 7. 7. 23:44
https://www.acmicpc.net/problem/2550
2550번: 전구
첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력
www.acmicpc.net
풀이
사용한 알고리즘 : LIS
풀이 전략
import sys
input=sys.stdin.readline
N=int(input())
switch=list(map(int,input().split()))
bulb=list(map(int,input().split()))
arr=[]
for i in switch:
arr.append(bulb.index(i))
length=[0]*N
preNode=[]
for i in range(N):
preNode.append(i)
for i in range(N):
length[i]=1
k=0
for j in range(i):
if arr[j]<arr[i]:
if length[i]<length[j]+1:
length[i]=length[j]+1
preNode[i]=j
temp=length.index(max(length))
result=[]
x=temp
while True:
result.append(switch[x])
if preNode[x]==x:
break
x=preNode[x]
result.sort()
print(max(length))
for i in result:
print(i,end=' ')