백준 2353 - 반도체 설계(C++)

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

2352번: 반도체 설계

문제 조건

출력 예시

선을 꼬이지 않고 연결할 수 있는 최대 갯수를 구하는 방법

위와 같이 연결되어 있다고 했을 때

1. 왼쪽을 기준으로 오름차순 정렬을 한다.(문제에선 이미 되어 있음으로 생략)

2. 오른쪽 수열에서 가장 긴 증가하는 부분 수열을 찾는다.

   ex) 4 2 6 3 1 5 -> 2 3 5

 

https://junseok.tistory.com/23 와 비슷한 lower_bound를 사용했습니다. 이분 탐색 부분은 이 블로그를 참고해주세요!

백준 12015 - 가장 긴 증가하는 부분 수열2(복습)

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <cstring>
#include <string.h>
using namespace std;


int N;
int line[40001];
vector<int> connect;

void binary_search(int x) {
    int low = 0;
    int high = connect.size() - 1;
    int ret = 4000000;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (connect[mid] >= x) {
            if (ret > mid) ret = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }
    connect[ret] = x;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> line[i];
    }
    connect.push_back(line[0]);
    for (int i = 1; i < N; i++) {
        if (connect.back() < line[i]) connect.push_back(line[i]);
        else binary_search(line[i]);
    }
    cout << connect.size();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!