[BOJ]2550. 전구

문제:

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

출력:

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

풀이방법:

 겹치지 않도록 최대한 많이 선택해야 하는 문제다. 이는 곧 가장 긴 증가하는 부분 수열(LIS) 문제와 같다. 따라서 LIS 알고리즘을 사용하여 가장 긴 증가하는 부분 수열을 찾으면서 그 부분 수열의 번호들도 같이 찾는 문제에 해당한다.

 LIS 문제를 해결하는 방법에는 여러가지가 있지만, 이 문제에서는 bisect를 이용했다. 이 방법의 핵심은 최대한 작은 수들을 고르는 것이 가장 긴 증가하는 부분 수열을 만들기 유리하다는 것이다. 1 2 7 이라는 부분 수열과 1 2 4 이라는 부분 수열이 있을 때 후자의 경우가 더 긴 부분 수열을 만들 확률이 높다는 것이다. 따라서 입력으로 들어오는 배열에서 bisect을 이용하여 계속해서 배열을 최신화한다.

하지만 이 때 만드는 배열은 실제 가장 긴 증가하는 부분 수열은 아니다. 이는 길이만을 알 수 있기 때문에, 만드는 동시에 위치 정보도 같이 추가하여 마지막에 실제 가장 긴 부분수열을 찾을 수 있도록 한다. 이 때 사용하는 것이 idx 배열이며 , start의 각 원소가 몇 번째 자리에 들어가는지에 대한 여부다. idx=[0,0,1,1,2]라는 것은 2가 0번째, 4가 0번째, 1이 1번째, 5가 1번째, 3이 2번째 자리에 각각 들어가게 된다는 것이다. 따라서 역순으로 idx 배열을 탐색하면서 2, 1, 0이 먼저 나오는 순서로 넣는 것이 최종 답에 해당한다. (나중에 들어간 것이 마지막에 남아 있는 수들이기 때문)

import bisect
 
N = int(input())
start = list(map(int,input().split()))
end = list(map(int,input().split()))
 
d = [0 for _ in range(N+1)]
 
for i, v in enumerate(end):
    d[v] = i+1
    
LIS = []
idx = []
 
for s in start:
    now = d[s]
    if len(LIS)==0 or LIS[-1] < now:
        idx.append(len(LIS))
        LIS.append(now)
    else:
        cur = bisect.bisect_left(LIS, now)
        if len(LIS)==cur:
            LIS.append(now)
        else:
            LIS[cur] = now
        idx.append(cur)
 
print(len(LIS))
 
answer = []
pos = max(idx)
for v in idx[::-1]:
    N -= 1
    if pos == v:
        answer.append(start[N])
        pos -= 1
        
print(*sorted(answer))

문제링크:

https://www.acmicpc.net/problem/2550

2550번: 전구