Problem
https://www.acmicpc.net/problem/3006
https://www.acmicpc.net/problem/2618
이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.)
도로의 개수 N(5≤N≤1,000), 사건의 개수 W(1≤W≤1,000)
전체 탐색으로는 2^40으로 ac를 받을 수 없다
https://www.acmicpc.net/problem/1208
공집합이 아닌 부분집합 중 합이 S가 되는 부분 집합의 개수
1≤N≤40, |S|≤1,000,000
전체 탐색으로는 2^40으로 ac를 받을 수 없다
집합을 A={}, B={} 반으로 나눈다. http://kimbregas.tistory.com/18
1 <= i <= j <= n such that Si - Sj-1 = S
https://www.acmicpc.net/problem/2003
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수
N(1≤N≤10,000), M(1≤M≤300,000,000)
연속된 수들의 합이기 때문에 two pointer 접근
O(n)
https://www.acmicpc.net/problem/13555
길이가 N인 두 수열 A1, A2, …, AN와 정수 K 주어진다. 이 때, 수열 A의 부분 수열 중에서 길이가 K이면서 증가하는 부분 수열의 개수를 구한다