[2352] 반도체 설계(C++)

문제

2352번: 반도체 설계

 

 

🔎 해결 방법

이 문제는 [11053] 가장 긴 증가하는 부분 수열과 같이

왼쪽 포트는 이미 오름차순으로 정렬이 되어 있으므로

이와 연결된 두번째 포트가 어떻게 해야 가장 긴 증가하는 부분 수열을 이루는지를 찾으면 된다.

 

그래서 처음에는 [11053] 가장 긴 증가하는 부분 수열 문제를 해결한 것과 같이 이중 for문을 사용한 dp로 해결하려고 했다.

하지만 틀렸습니다가 떠서 질문들을 찾아보니

대부분 "LIS" 라는 알고리즘을 사용하여 문제를 해결했었다.

그래서 LIS가 무엇인지에 대해 찾아보았다

 

 

❓LIS(Logest Increasing Subsequence)

말 그대로 가장 긴 증가 부분 수열을 찾는 방법인데, 찾는 방법에는 크게 두 가지가 있다.

1. Lower Bound를 이용한 방법

2. 인덱스 트리를 이용한 방법

 

나는 1번을 사용한 문제 해결 방법을 찾아보았다.

Lower Bound를 이용한다는 것은 말 그대로 가장 낮은 경계, 즉 내가 들어갈 수 있는 위치 중에 가장 값이 작은 인덱스를 찾는 것이다.

위의 인덱스를 찾기 위해  lower_bound() 라는 함수를 사용하는데

이 함수는 벡터 또는 배열의 처음부터 끝까지 탐색하며, 자신보다 크거나 같은 값을 가지는 iterator를 반환한다.

iterator는 객체 지향적 프로그래밍에서 배열이나 그와 유사한 자료 구조의 내부의 요소를 순회하는 객체이기 때문에

인덱스의 위치를 얻고 싶다면

it = lower_bound(sequence.begin() + 1, sequence.end(), port[i]) - sequence.begin();

위와 같이 마지막에 벡터의 시작 주소를 꼭! 빼줘야 한다.

 

문제의 예시를 보면 우리는 [4, 2, 6, 3, 1, 5] 중에 가장 긴 증가하는 부분 수열의 길이를 찾으면 된다.

우선 sequence 벡터에 port[1]을 삽입한 뒤, port[2]와 sequence[1]을 비교한다.

 

이때, port[2]의 값이 sequence 벡터의 마지막 원소보다 작으므로, lower_bound를 사용하여 적절한 위치를 찾은 뒤 덮어쓰면

이렇게 된다. 이제 port[3]과 sequence[1]을 비교하면 port[3]이 더 크므로 

그냥 삽입해주면 된다.

 

이제 port[4]와 sequence[2] 중에 port[4]이 더 작으므로, 적절한 위치에 삽입하고 덮어쓰면

이렇게 된다.

 

마찬가지로 port[5]와 sequence[2]를 비교하면 port[5]가 더 작으므로 계산하면

위와 같이 된다. 

 

그리고 port의 마지막 원소도 똑같이 비교해주면

최종적으로는 위와 같이 된다.

 

하지만!

이것은 정답이 아니다. 문제에서 도출하면 되는 정답은 맞지만 실제로 우리가 선택해야 하는 오른쪽 포트는

1, 3, 5가 아니라

2, 3, 5가 되어야 겹치지 않는다. 

그냥 어떤 포트를 선택하는지는 중요하지 않기 때문에 시간 복잡도를 줄이기 위해 다들 이 방법을 사용하는 것 같다...

 

 

💡 내 코드(C++)

// [2352] 반도체 설계
// https://www.acmicpc.net/problem/2352
// 다이나믹 프로그래밍, 그리디 알고리즘, LIS

#include <iostream>
#include <vector>
#include <algorithm> // lower_bound()

using namespace std;

int main(void)
{
    int n, port[40002], it;
    vector <int> sequence;
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> port[i];
    }
    
    // dp 벡터의 시작 인덱스를 1로 만듦
    sequence.push_back(0); sequence.push_back(port[1]);
    for(int i = 2 ; i <= n ; i++) {
        if(port[i] > sequence[sequence.size() - 1]) {
            sequence.push_back(port[i]);
            continue;
        }
        // 1. sequence의 마지막 원소보다 port[i]가 크다면 sequence 벡터에서 적절한 위치를 찾고
        it = lower_bound(sequence.begin() + 1, sequence.end(), port[i]) - sequence.begin();
        
        // 2. 덮어쓰기
        sequence[it] = port[i];
    }

    cout << sequence.size() - 1 << endl;
}