-
[BOJ] 2565 : 전깃줄
2565 : 전깃줄 풀이 LIS를 구해주자! 주어진 두 축을 주어진 선으로 연결했을 때 겹치는 선이 없어야 한다! 한 축 x를 기준으로 잡아 pair를 정렬해주자. 이제 정렬한 축 x를 기준으로 한바퀴 쭉 돌면서 순서대로 마주치는 y축에 대해서 LIS를 수행해주자! 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, len, lis[100]; pair<int, int> a[100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d",...
-
[BOJ] 1965 : 상자넣기
1965 : 상자넣기 풀이 lower bound를 써주자! 더 큰 상자가 최소 어디에 들어갈 수 있는지 lower bound로 찾으면 된다! O(n^2) dp대신에 lower bound를 써주면 O(nlogn)에 풀 수 있따! 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, len, a[1001]; int main() { scanf("%d", &n); while (n--) { int tmp; scanf("%d", &tmp); auto it = lower_bound(a, a + len, tmp); if (*it == 0) len++; *it = tmp; } printf("%d", len); return 0; } 아무말...
-
[BOJ] 2532 : 먹이사슬
2532 : 먹이사슬 풀이 문제를 풀고 나서 다른 분들의 코드를 보다가 lower_bound를 저렇게 쓸 수 있다는 사실에 감명받았다. 양수가 음수로 변하면, 양수일 때 더 큰 수가 음수에선 더 작은 수가 되는데 양수 중에서 작은 수와 음수 중에서 가장 작은 수를 고르게 되면 넓은 범위를 찾게 된다. *lower_bound(res, res + i, now) = now;를 통해 먹이사슬인지 판단할 수 있다. 새로운 데이터가 쌓이지 못하고 덮어쓰게 되면 INF의 값이 배열의 뒤쪽에 누적되게 되고, INF의 lower_bound가 답이 된다. 코드...