문제 링크 http://icpc.me/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택과 분할 정복을 이용하여 풀 수 있다. 스택을 이용한 풀이는 O(N)에 풀 수 있지만 아이디어를 떠올리기 힘들고, 분할 정복은 O(NlogN)에 풀 수 있지만 세그먼트 트리를 알아야 한다. 분할 정복 구간 [l, r]에서 가장 큰 직사각형의 넓이는 (가장 작은 기둥 높이) * (r - l + 1) 그렇기 때문에 가장 작은 기둥 왼쪽, 가장 작은 기둥 ..

문제 링크 http://icpc.me/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 풀이 dp와 분할 정복을 이용하여 풀이할 수 있다. 분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자. dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2) 위의 식에 n-2를 대입한식과 위의 식을 빼면 dp[n] = 4 * dp[n-2] - dp[n-4]가 나온다. 행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다. 코드 #include #include using namespace st..