알고리즘/문제풀이 - 백준

백준 2565 전깃줄

문제 : https://www.acmicpc.net/problem/2565 서론LIS 문제라는것을 알았는데도 풀이를 떠올리지 못했다.전깃줄을 제거하는게 아니라 역으로 교차하지 않는 전깃줄을 세는것을 알고 난 후 문제의 예제 그림을 통해 이해할 수 있었다. 풀이주어진 입력을 문제의 예제 그림과 같이 만들기 위해 A위치를 기준으로 오름차순 정렬한다.그 후 B 위치를 기준으로 LIS정렬 해주면 된다. 구현//c++ #include #include using namespace std; typedef struct { int first; int second; }st; int dp[102]; st line[102]; bool compare(st a, st b) { return a.first < b.first; } i..

2019. 7. 9. 13:54