백준 1365 - 꼬인 전깃줄(C++)

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

1365번: 꼬인 전깃줄

문제 조건

출력 예시

https://junseok.tistory.com/73

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

이 문제와 비슷한 문제였습니다! 자세한 것은 링크된 블로그를 참고해주세요.

 

 

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

int N;
int ele[100001];
vector<int> ele_line;

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

void solve() {
	ele_line.push_back(ele[0]);
	for (int i = 1; i < N; i++) {
		if (ele_line.back() < ele[i]) {
			ele_line.push_back(ele[i]);
		}
		else {
			binary_search(ele[i]);
		}
	}
	cout << N - ele_line.size();
}

int arr[101][101];
int n;
int c = 1;
int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> ele[i];
	}
	solve();
	return 0;
}

 

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