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

백준의 반도체 설계(2352) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

서로 꼬이지 않게 포트를 연결할 떄, 최대 몇 개 까지 연결 할 수 있는지 구해야 하는 문제이다.

포트가 꼬이지 않게 연결 한다는 것은, 연결되어 있는 포트 번호들이 오름차순으로 정렬되어 있어야 한다는 것을 의미한다.

극단적으로 아래와 같은 예를 보자.

.

위에 그림에서 포트 번호를 위에서부터 1번, 2번, 3번, ... , 5번으로 번호를 붙여본다면, 연결되어 있는 포트 번호는

{ 2 , 3 , 1 , 5, 4 } 가 된다. 그리고 위의 상태에서 가장 많은 포트를 연결하면서 꼬이게 연결하려면 다음과 같은 2가지 상황이 가능하다.

.

그럼 위의 상황에서 연결되어 있는 포트 번호들만 적어보면 { 2 , 3 , 4 } 와 { 2 , 3 , 5 } 가 된다.

즉 ! 연결되어 있는 포트 번호들이 오름차순으로 정렬만 되어 있다면 이는 꼬이지 않게 포트를 연결할 수 있다는 것을 의미한다.

그런데 ! 우리는 이 중에서도 "가장 많은 포트를 연결" 해야 하기 때문에, "가장 긴 증가하는 부분 수열"을 찾으면 되는 것이다.

실제로, 우리가 위에서 든 예시로 보면 { 2 , 3 , 1 , 5 , 4 } 에서 가장 긴 증가하는 부분 수열은 { 2 , 3 , 4 } 혹은 { 2 , 3 , 5 } 가 된다.

그럼 우리는 입력으로 주어지는 배열에서 "가장 긴 증가하는 부분 수열의 크기" 를 구하면 된다.

구하는 방법으로는 O(N^2)만에 구하는 방법도 있고, O(NlogN) 시간 안에 구하는 방법도 존재한다.

그런데, 이 문제는 입력으로 주어지는 배열의 크기가 40,000 이다. O(N^2)의 알고리즘을 사용한다면, 10억번이 넘는 연산을 필요로 해서 시간초과가 발생하게 된다.

따라서, 우리는 O(NlogN) 시간안에 해결할 수 있는 알고리즘을 사용해야 한다.

구체적인 풀이는 아래에 링크가 걸린 문제를 풀어보고 와도 좋고, 풀지 않더라도 풀이를 통해서 확인하길 바란다.

아래의 문제가, 주어진 수열에서 "가장 긴 증가하는 부분 수열의 크기"를 O(NlogN) 만에 구하는 알고리즘을 이용해서 구해야 하는 문제이다. 즉, 이 문제와 풀이가 동일하다는 것이다.

[ 백준 - 가장 긴 증가하는 부분수열3(12738) 문제 바로가기 ]

[ 백준 - 가장 긴 증가하는 부분수열3(12738) 풀이 바로가기 ]

[ 소스코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
 
#define endl "\n"
#define MAX 40010
using namespace std;
 
int N;
int Arr[MAX];
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i]) V.push_back(Arr[i]);
        else
        {
            int Pos = lower_bound(V.begin(), V.end(), Arr[i]) - V.begin();
            V[Pos] = Arr[i];
        }
    }
    cout << V.size() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}