반응형
문제 출처 :
https://www.acmicpc.net/problem/1365
알고리즘 분석 :
문제 해결에 필요한 사항
1. LIS 알고리즘 :: http://www.crocus.co.kr/583
LIS로 해결할 수 있는 문제이다.
문제 예제처럼 2 3 4 1을 보자.
lis 배열에 들어오는 과정을 보면
2
2 3
2 3 4
1 3 4
이렇게 변한다.
1이 즉 4번째에 있어야 하는데 1번째로 왔다. 결국 3칸 움직였다는 의미는 3개의 선이 꼬였다는 것이다.(1과 2,3,4)
다른 예제를 보자
2 5 3 4 1이 있다고 생각하면
2
2 5
2 3 :: 3번째에 있어야 하는 것이 2번째로 왔다. 즉, 3과 5가 꼬여있다는 의미이다.
2 3 4
1 3 4 :: 4번째에 있어야 할 것이 1번째로 왔다. 즉, 3개의 선이 꼬였다는 의미이다.
(그림으로 그리면 총 4개의 선이 꼬여있지만, 그림을 순차적으로 그리면 이미 2->5선은 지워진 상태이라 생각할 수 있고
결국 3개의 선이 꼬여있는 것이다.)
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | /* * Problem :: [1365번] 꼬인 전깃줄 * Date :: 2017/03/17 * link :: https://www.acmicpc.net/problem/1365 * * http://www.crocus.co.kr */ #include <iostream> #include <cstdio> using namespace std; int arr[100001]; int lis[100001]; int _lower_bound(int start, int end, int target) { int mid; while(start < end) { mid = (start + end) / 2; if(lis[mid] < target) start = mid + 1; else end = mid; } return end + 1; } int main() { int n; scanf("%d",&n); for(int i = 0 ; i < n ; i ++) scanf("%d",&arr[i]); int pLis = 0, pArr = 1, cnt = 0; lis[pLis] = arr[0]; while(pArr < n) { if(lis[pLis] < arr[pArr]) lis[++pLis] = arr[pArr]; else { int ans = _lower_bound(0, pLis, arr[pArr]); lis[ans-1] = arr[pArr]; cnt++; } pArr++; } printf("%d",cnt); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1325번] 효율적인 해킹 (0) | 2017.03.19 |
---|---|
[10825번] 국영수 (0) | 2017.03.18 |
[3176번] 도로 네트워크 (0) | 2017.03.17 |
[11054번] 가장 긴 바이토닉 부분 수열 (0) | 2017.03.17 |
[11722번] 가장 긴 감소하는 부분 수열 (0) | 2017.03.17 |