2601번: 도서실카펫 (acmicpc.net) 2601번: 도서실카펫 모든 사각형의 좌표는 1,000,000 보다 작은 음이 아닌 정수이고 가로 세로의 길이는 1,000,000 보다 작은 양의 정수이다. 얼룩 직사각형은 서로 겹치지 않지만 접할 수는 있다. 얼룩 직사각형과 카펫 www.acmicpc.net 알고리즘 태그 : 레이지 세그먼트 트리, 스위핑 시간 복잡도 : \(O(NlogN+MlogM)\) 각 얼룩 마다 어디에 카펫을 설치할 경우 이 얼룩이 지워진다는 것을 직사각형 모양의 범위로 표현할 수 있다. 이제 이 범위들을 가지고 스위핑을 하며 구간 업뎃을 해서 각 업뎃이 끝났을 때 마다 전체 구간의 최댓값을 구해주면 된다. #include #define x first #define y second..
https://www.acmicpc.net/problem/17493 17493번: 동아리 홍보하기 1, 4, 7번 전봇대에 전단지를 붙이면, 모든 곳에서 전단지를 볼 수 있다. www.acmicpc.net 보통 저런 문제들이 트리 dp형태인데, dp테이블을 직관적으로 세워보자. \(dp[i][0] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드는 자식들 중 한 노드에 전단지가 붙여져있을 때, 최소 전단지 수 \(dp[i][1] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드에 전단지를 붙일때, 최소 전단지 수 \(dp[i][2] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드의 부모가 전단지가 붙여져있을 때, 최소 전단지 수 이렇게 \(dp\)식을 세..
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net \(N\)개의 수를 그리디적으로 적절히 정렬할려고 한다. 어떤 두 수 \(A\), \(B\) 에 대해 \(AB\)랑 \(BA\) 중에 더 크게 되도록 정렬을 해주면 된다. 만약, \(AB\) > \(BA\) 라면 \(A\), \(B\) 순으로 정렬해주면 되고, 반대라면 \(B\), \(A\) 순으로 정렬해주면 된다. 자리수를 구할때 입력받은 수가 0인 경우에 0자..
https://www.acmicpc.net/problem/8146 8146번: Tetris Attack A puzzle called "Tetris Attack" has lately become a very popular game in Byteotia. The game itself is highly sophisticated, so we shall only introduce its simplified rules: the player is given a stack of 2n elements, placed one on another and marked with n www.acmicpc.net 일단 여러가지 관찰을 해본게 있는데, 1. \(x..y..x..y\)의 경우엔, \(x..x...y..y\) 경우가 되거..
https://www.acmicpc.net/problem/6164 6164번: Hotel The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacatio www.acmicpc.net 딱 보면 뭔가 금광세그를 박아야 할 것 같은 느낌이 든다. 그래서 한번 금광세그를 박았을때 뭘 어떻게 해야 할지를 적어보면, struc..
https://www.acmicpc.net/problem/18919 18919번: Allowed Swaps You are given a permutation of length $N$ and a list of allowed swaps. Each swap is defined by two distinct integers between 1 and $N$, inclusive --- positions in the permutation that can be swapped. Your task is to sort the permutation using no more than www.acmicpc.net \(x, y\) 쌍이 들어오면 \(x\) 와 \(y\)를 이어주는 간선을 만들어준다. 그러면, 그래프가 형성되는데, 사..
https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net '('을 1, ')'을 -1이라 가정한다. 만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다. 이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다. 따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다..
https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 이 문제는 언뜻 보면 어려워 보이는데, 사실 \((2000/2)^{2} = 10^{6}\) 임을 알면 왼쪽에 1000개, 오른쪽에 1000개에 적당한 약의 개수를 넣으면 \(10^6\) 개를 만들 수 있을 것 같다. 어떤 약의 수 X만큼을 주기 위해 X를 1000으로 나눈 몫과 나머지에 대한 식을 세워보자. $$X = 1000*b + r$$ 왼쪽엔 1000짜리 1000개, 오른쪽에는 1짜리 1000개를 넣으면, 원하는 수 만큼의 약을 담을 수 있다. #include using nam..
https://www.acmicpc.net/problem/17958 17958번: Cycle String? In the first example, substrings of the restored string are: “abbab”, “bbabc”, “babcb”, “abcbc”, “bcbcc”, “cbccb”, “bccba”, “ccbab”, “cbabb”, “babba”. Note that the first example does not contain repetitions, however www.acmicpc.net 일단 \(NO\)가 되는 조건을 알아보자. 1. 등장하는 문자가 1개인 경우 ex)\(aa...a\) 2. 등장하는 문자가 2개고, 한 문자가 \(2N-2\)개 이상인 경우 ex) \(aa..
https://www.acmicpc.net/problem/4011 4011번: 기름 파기 첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각 www.acmicpc.net 구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다. 총 6가지 경우가 있다. 왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다. DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 ..
- Total
- Today
- Yesterday
- 세그먼트 트리
- ABC
- hyper
- 김춘배
- 수열과 쿼리
- Rabin-Karp
- codeforces
- 쿼리
- Constructive
- BOJ
- 알고리즘 문제 풀이
- DP
- 앳코더
- combination
- 하이퍼
- Offline Dynamic Connectivity
- 누적 합
- 냄새 싫어
- 비요뜨 존맛
- PS
- AtCoder
- 정렬
- 1909
- 오일러 경로
- 비요뜨
- gunwookim
- 스택
- 간단한 풀이
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |