백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..

이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다. 이 지점에서 Segment Tree 기법을 생각했어야 한다. Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다. 다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데 이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다. 또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다. 요약하자면 다..

문제 상황을 이해하려고 끄적거리다보면 숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다. 즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다. 이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다. 1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지 2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지 이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다. 또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와..

전형적인 Segment tree 문제이다. 관련한 개녕은 www.crocus.co.kr/648 에 잘 나와있으므로 참고하도록 하자. Init, sum, update함수를 적당히 잘 구현해서 풀어주면 되는 문제이다. 중간중간에 숫자를 수정하고 구간 합을 구하는 지점에서 세그먼트 트리 문제임을 눈치챘어야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); typedef long long ll; using namespace std; ll arr[1000000]; ll tree[1000000 * 4]; ll init(ll start, ll end, ll node){ if(start == end) return tree..

분할정복의 대표적인 예시인 L-트로미노 타일링 문제이다. (사실 그냥 풀라고 했으면 못풀었을 듯) 접근 방법은 다음과 같다. (자세한 내용은 wogud6792.tistory.com/64 참고) 1. 전체 타일을 4등분해서 하수구의 위치를 찾는다. 2. 하수구가 없는 영역들은 가안 안쪽 타일을 색칠한다. 3. 나눠진 각 타일을 기준으로 1,2 과정을 반복한다.(다만, 색칠된 타일은 하수구와 동일하게 취급해서 진행해주면 된다.) 그리고 가장 작은 단위인 2 x 2가 나올 때 직접 처리를 해주면 된다. #include #include #include #include #include #include using namespace std; int check_count = 1; int dp[129][129]; int..

문제 자체는 대표적인 분할정복 예제 중 하나인 거듭수에 대한 계산이다. 그런데 피보나치를 저렇게 나타낼 수 있는 것에 대해서 되게 신기했다. n어 엄청나게 커도 게속해서 절반 쳐주면서 계산하면 O(lgn)으로 처리할 수 있다. #include #include #include #include #include typedef long long ll; using namespace std; void fib_set(int n, vector &dp){ if(n == 1) { dp[0] = 1; dp[1] = 1; dp[2] = 1; return; } if(n % 2 == 0){ vector data(4, 0); fib_set(n / 2, data); dp[0] = (data[0] * data[0] + data[1] ..

문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로 만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다. 따라서 이분탐색의 upper_bound를 활용해주면 된다. Upper_bound의 대략적인 skeleton code는 다음과 같다. // Upper_bound (이분탐색에서의 상계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start M >> N; vector data_store; for(int i = 0; i > temp; data_store.push_back(temp); } sort(data_..

전형적인 이분탐색의 lower_bound 형태이다. 전체적인 스켈레톤은 다음과 같다. 자세한 설명은 viyoung.tistory.com/77?category=284521 참고 // Lower_bound (이분탐색에서의 하계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start < end){ mid = (start + end) / 2; if(card[mid] < compare_value){ start = mid + 1; } else{ end = mid; } } 사실 이 문제는 오버 플로우 때문에 개고생했다.. 처음에는 end값을 리터럴로 잡으려고 하다가 계속 틀려서 input값을 기준으로 최댓값을 보정하니까 맞았다. (생각보다 숫자..