[C/C++] 백준 #2352 반도체 설계(가장 긴 증가하는 부분수열)

가장 긴 증가하는 부분수열 문제는 백준 사이트에서 자주 접할 수 있는 문제입니다.  이 알고리즘을 잘 이해하면, 풀 수 있는 문제들이 많이 있습니다.

 

증가하는 부분수열 중 하나를 출력하라면 조금 골치가 아프겠지만, 현재 이 알고리즘을 이용해서 부분수열도 출력할 수 있습니다.

 

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

2352번: 반도체 설계

 

반도체에서 서로 라인이 겹치지 않도록 설계하는 것은 중요한 문제입니다.  실제로는 다층기판을 이용하기 때문에 라인이 겹쳐도 상관이 없지만, 단면기판을 사용한다면, 좀 고려가 필요합니다.

 

 

가장 긴 증가하는 부분수열 알고리즘을 설명하는 게시물은 아래를 참고해주시길 바랍니다.  문제의 유형도 거의 같습니다.

https://sdev.tistory.com/577

[C/C++] 백준 #1365 꼬인 전깃줄(가장 긴 증가하는 부분수열)

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2352 - Semiconductor Design
//        - by Aubrey Choi
//        - created at 2019-07-10
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, s, cur = 0;
    static int dp[40001];
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &s);
        if(cur == 0 || dp[cur - 1] < s) dp[cur++] = s;
        else
        {
            int *p = std::lower_bound(dp, dp + cur, s);
            *p = s;
        }
    }
    printf("%d\n", cur);
}