DP[n] : n번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 DP[n] = DP[n-1]+DP[n-2]+...+DP[1] 이라는 식이 나오는데 DP[n-1] = DP[n-2]+DP[n-3]+...+DP[1] DP[n-2] = DP[n-3]+DP[n-4]+...+DP[1] . . . DP[1] = 1 이제 DP[1]부터 DP[n-1]을 DP[n]의 식에 대입해 보면 DP[n] = 2(DP[n-2]+DP[n-3]+...+DP[1]) = 2^2(DP[n-3]+DP[n-4]+...+DP[1]) = 2^3(DP[n-4]+DP[n-5]+...+DP[1])... =2^(n-2)DP[1] 가 나옵니다. DP[1] = 1 이기 때문에 답은 2^(n-2) 가 됩니다. 각 테스트 케이스마다 2^(n-2)를..
Mo's algorithm 을 사용하는 문제다. 와아아아아아아앙 짝짝짝짝 각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다. 이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다. 이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다. 이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다. 자세한건 코드를 보자. #include using namespace std; list dq[300005]; int n,k,Q,val,sz; int ans[300005],a[300005]; int b[300005],cnt[5000005]; struct Query { ..
세 용액은 여러가지 풀이가 있습니다 1. 트리를 이용한 풀이 2. 이분탐색을 이용한 풀이 3. 양방향 탐색을 이용한 풀이 이 블로그에서는 양방향 탐색을 이용한 풀이 입니다! n번을 돌면서 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾는 풀이입니다! 총 O(n^2) 이 되겠네요! #include using namespace std; /// 풀이 : 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾을거에요! int n; long long a[5005]; int main() { cin >> n; for(int i = 1;i > a[i]; } sort(a+1,a+n+1); /// 정렬을 해야 가능해요! int idx1 = n-2,idx2 = n-1,idx3 = n; /// 여기에 세 용액의 인덱스가 들어..