백준 2352번 반도체 설계

문제 링크입니다: https://www.acmicpc.net/problem/2352

http://jaimemin.tistory.com/430와 유사한 문제로 LIS 문제였습니다.

하지만 기존의 문제는 O(n^2) 안에 풀어도 되는 문제였지만 이번 문제는 O(nlogn) 안에 풀어야하는 문제였습니다.

O(nlogn) 안에 푸는 문제는 lower_bound 함수를 이용해야 하는데 http://dyngina.tistory.com/16를 참고했습니다.

포스팅을 참고하면 인덱스 배열을 통해 푸는 방법도 있지만 아직 인덱스 배열을 접해본 적이 없으므로 다음 기회에 인덱스 배열을 사용해보도록 하겠습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 40000;

 

int N;

int connect[MAX + 1];

int cache[MAX + 1];

 

//O(n^2)는 시간초과

/*

int portLIS(int leftPort)

{

        int &result = cache[leftPort + 1];

        if (result != -1)

               return result;

 

        result = 0;

        for (int next = leftPort + 1; next < N; next++)

               //왼쪽 포트번호가 1이거나 다음 연결할 포트번호가 더 커 꼬이지 않을 경우

               if (leftPort == -1 || connect[leftPort] < connect[next])

               {

                       int candidate = 1 + portLIS(next);

                       result = max(result, candidate);

               }

        return result;

}

 

int main(void)

{

        cin >> N;

       

        for (int i = 0; i < N; i++)

               cin >> connect[i];

 

        memset(cache, -1, sizeof(cache));

        //원래대로라면 idx=1부터 입력받으므로 0부터 시작해야하지만

        //connect 배열을 idx=0부터 입력받았으므로 -1에서 시작

        cout << portLIS(-1) << endl;

        return 0;

}

*/

 

//O(nlogn) 안에 실행되어야함

int portLIS(void)

{

        //초기 값

        cache[1] = connect[1];

        int length = 1;

        for (int i = 2; i <= N; i++)

        {

               if (cache[length] < connect[i]) //선이 안 꼬일 경우 추가하고 continue

               {

                       cache[++length] = connect[i];

                       continue;

               }

               //i번째 왼쪽 포트에 연결되어있는 오른쪽 포트의 번호보다 작지 않은 최초의 위치 탐지

               int idx = lower_bound(cache + 1, cache + length + 1, connect[i]) - cache;

               cache[idx] = connect[i];

        }

        return length;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 1; i <= N; i++)

               cin >> connect[i];

 

        cout << portLIS() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~