2550. 전구 (Python)
2550번: 전구 N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 www.acmicpc.net 풀이 LIS를 사용하여 해결하는 문제다. LIS는 여기를 참고하자. 문제는 여기에서 LIS의 길이뿐만 아니라 LIS에 포함되는 원소까지 구해야 한다. 일단 LIS를 구하는 대상이 되는 배열은 n번의 스위치가 전구 리스트에서 몇 번째에 있는지를 나타내는 인덱스 리스트이다. 문제의 예제를 보면 스위치 리스트 [2, 4, 1, 5, 3]은 각각 전구 리스트에서 [4, 0, 2, 1, 3] 인덱스에 존재한다. 따라서 [4, 0, 2, 1, 3]에 대해서 LIS를 구하고 각각에 ..
2022. 4. 28.
