[백준 21234] Just Green Enough
문제 www.acmicpc.net/problem/21234 알고리즘 스위핑 풀이 N * N 사각형안에 값들이 주어집니다. 부분 직사각형안에 최솟값이 100이 될 수 있는 직사각형의 갯수를 구하는 문제입니다. 사각형을 결정하기 위해선 상하좌우의 변이 필요합니다. 다르게 말하자면 브루트포스로 해결하기 위해선 $O(N^4)$의 시간복잡도가 필요하므로 시간초과입니다. 한 직사각형의 위와 왼쪽변을 결정했다고 가정하겠습니다. 이 변들을 포함하며 최솟값이 100이 되는 직사각형들을 찾기 위해서는 왼쪽변보다 오른쪽에 위치한 변들을 살피며 그때 아래변들을 살펴보면 됩니다. 이 과정은 위에서 언급한대로 $O(N^4)$의 시간복잡도를 필요하지만 아래변들을 살필 때 우리가 찾는 것은 가장 높은 100의 위치(A)와 포함해서는..
Algorithm
2021. 3. 31. 13:58
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Fenwick
- union find
- dijkstra
- 2-SAT
- 트라이
- hld
- Suffix Array
- kmp
- Segment tree
- 정렬
- sorting
- dfs
- sweeping
- spring boot
- 이분매칭
- 이분탐색
- 동적계획법
- 좌표압축
- spring
- SCC
- implementation
- DP
- greedy
- 세그먼트트리
- string
- bfs
- 스위핑
- 펜윅트리
- knapsack
- Oracle
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함