BOJ 10070 - 벽 (D5)
사용 알고리즘 segment tree + lazy propagation 풀이 뭔가 쉬워보이긴 한데 해보면 바로 해결되지는 않는 그런 문제이다. 세그먼트 트리의 각 노드는 그 노드가 담당하는 구간의 수 범위를 저장한다. 이제 얘를 어떻게 업데이트하고 전파할지가 문제이다. 업데이트할 노드의 원래 수 범위가 [L,R]이고 업데이트할 값이 X라 하자. 일단 이 노드가 업데이트할 구간에 완전히 포함되는 경우를 보자. op = 1의 경우는 L = max(L,X), R = max(R,X)로 하면 된다. 마찬가지로 op = 2는 L = min(L,X), R = min(R,X)로 하면 된다. 업데이트할 구간에 걸치면, 자식 노드들을 봐야하는데 이때 원래 자식 노드들의 [L,R]과 현재 노드의 [L,R]을 비교해서 자식 ..
더보기
BOJ 16682 - 삼원색 (D5)
최근에 세그먼트 트리 문제를 많이 푸는데, 그 이유는 nypc 2-A에서 세그먼트 트리에 당했기 때문이다. 사용 알고리즘 Segment Tree + 좌표압축 + 포함배제 풀이 앞으로는 Cyan, Magenta, Yellow, Red, Green, Blue, Black을 각각 C, M, Y, R, G, B, K라 부를 것이다. 일단 문제를 봤을 때, 색깔을 고려하지 않으면 떠오르는 문제가 하나 있다. https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,..
더보기
BOJ 14181 - 함수와 쿼리 (D3)
CHT 처음 배울때 봤다가 이게 왜 CHT지 하고 탈주했다. http://boj.kr/14181 14181번: 함수와 쿼리 첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 105)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 104) 다음 줄에는 쿼리의 개수 m (1 ≤ m ≤ 105)가 주어지고, 다음 m개의 줄에는 쿼리 www.acmicpc.net 풀이) Li-chao + Segment Tree 점화식을 세우기 영 쉽지 않아 보인다. 그러므로 정의에 따라 점화식을 관찰하자. $$ f(1,j)=a[j] $$ $$ f(2,j) = min (f(1,j), f(1,j-1)) + a[j] $$ $$ = min(2*a[j], a[j-1] + a[j]) $$..
더보기
