백준 2550번 전구 [C++]

 

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

2550번: 전구

#문제 간단 정리

 

#문제 해결 방법

1. 문제 이해하기

• 스위치와 전구가 있고, 각 스위치는 특정 전구를 켭니다.
• 스위치들을 함께 누르면, 그들의 연결선이 교차하지 않는 경우에만 전구들이 켜집니다.
• 우리의 목표는 최대한 많은 전구를 켜는 것입니다.
• 여기서 우리는 스위치의 순서대로 전구를 순서대로 나열했을때 가장 긴 증가는 부분수열을 구하면 가장 많이 킬 수 있는 전구의 개수를 알 수 있다는걸 파악 할 수 있습니다.(LIS)

2. 전구와 스위치 연결 관계 파악하기

• 각 전구가 몇 번째 스위치에 연결되어 있는지를 파악합니다. 이는 우리가 스위치를 눌렀을 때 어떤 전구가 켜지는지 알기 위함입니다.

3. 최장 증가 부분 수열(LIS) 개념 이해하기

• LIS는 주어진 순열에서 어떤 원소들을 선택했을 때, 선택된 원소들이 증가 순서를 유지하는 가장 긴 부분 순열을 의미합니다.
• 이 문제에서는 스위치와 전구의 연결선이 교차하지 않기 위해 LIS를 찾아야 합니다.

4. 문제 해결을 위한 동적 프로그래밍(DP) 사용하기

• DP를 사용해 각 스위치까지 고려할 때, 교차하지 않고 켤 수 있는 최대 전구 수를 찾습니다.
• 각 스위치에 대해, 그 스위치를 포함하는 최장 증가 부분 수열의 길이를 저장합니다.
• 이 과정에서, 각 스위치의 이전 스위치들과 비교하여, 연결선이 교차하지 않고 증가 순서를 만족하는 가장 긴 수열을 찾습니다.

5. 최장 증가 부분 수열 역추적하기

• DP를 통해 LIS의 길이를 찾은 후, 그 수열을 구성하는 스위치들을 역추적합니다.
• 역추적을 통해 어떤 스위치들을 눌러야 최대한 많은 전구를 켤 수 있는지를 파악합니다.

6. 결과 정리 및 출력하기

• 역추적한 스위치들을 오름차순으로 정렬합니다.
• 정렬된 스위치들을 출력하여, 눌러야 하는 스위치의 번호를 보여줍니다.

결론

• 이 문제는 스위치와 전구의 연결 관계를 분석하여, 전선이 교차하지 않는 방식으로 최대한 많은 전구를 켜는 스위치 조합을 찾는 것입니다.
• 동적 프로그래밍을 사용하여 각 스위치별로 교차하지 않고 켤 수 있는 최대 전구의 수를 계산하고, 최장 증가 부분 수열을 찾아 역추적하는 과정을 거쳐 최적의 스위치 조합을 결정합니다.
• 최종적으로, 이러한 스위치 조합을 오름차순으로 정렬하여 출력함으로써, 문제의 해결책을 제시합니다.

최장 증가 부분 수열(LIS) 문제에서의 DP

LIS 문제에서 우리는 주어진 시퀀스에서 가장 긴 증가하는 부분 수열을 찾아야 합니다. 이를 위해 DP를 사용하여 각 위치에 대해 최장 증가 부분 수열의 길이를 계산합니다.

DP 접근 방식:

1. 초기화: 길이가 N인 입력 시퀀스에 대해, 길이 N의 dp 배열을 생성하고 모든 요소를 1로 초기화합니다. dp[i]는 i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이를 저장합니다. 초기값 1은 각 원소가 자신만으로 구성된 부분 수열을 의미합니다.
2. 부분 문제 해결: i번째 원소에 대해, 0부터 i-1까지의 모든 j에 대해 다음을 수행합니다:
   • 만약 j번째 원소가 i번째 원소보다 작다면(arr[j] < arr[i]), j번째 원소를 포함하는 부분 수열에 i번째 원소를 추가할 수 있습니다. 이 경우, dp[i]는 dp[j] + 1과 현재 dp[i] 값 중 더 큰 값으로 업데이트됩니다. 이는 i번째 원소를 포함하여 얻을 수 있는 최장 증가 부분 수열의 길이를 의미합니다.
3. 전체 문제 해결: 모든 i에 대해 위의 과정을 수행한 후, dp 배열에 저장된 값들 중 최댓값이 전체 시퀀스의 최장 증가 부분 수열의 길이가 됩니다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> switches(N+1), bulbs(N+1), positions(N+1), dp(N+1), prev(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> switches[i];
    }
    for (int i = 1; i <= N; ++i) {
        int bulb;
        cin >> bulb;
        positions[bulb] = i;
    }
    for (int i = 1; i <= N; ++i) {
        bulbs[i] = positions[switches[i]];
    }

    fill(dp.begin(), dp.end(), 1);
    int maxLen = 0, lastIndex = 0;
    for (int i = 1; i <= N; ++i) {
        prev[i] = -1;
        for (int j = 1; j < i; ++j) {
            if (bulbs[j] < bulbs[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            lastIndex = i;
        }
    }

    cout << maxLen << endl;

    vector<int> sequence;
    while (lastIndex != -1) {
        sequence.push_back(switches[lastIndex]);
        lastIndex = prev[lastIndex];
    }

    sort(sequence.begin(), sequence.end());
    for (int i = 0; i < sequence.size(); ++i) {
        cout << sequence[i] << " ";
    }

    return 0;
}