Approach 다른 기준으로 쿼리를 관리하고 있으므로, Segment tree를 2개 각각 관리해주면 된다. 홀수의 구간합을 seg_odd, 짝수의 구간합을 seg_even에서 관리해주면 된다. 다만, update하는 과정에서 이전의 status가 변경될 수 있기때문에 하위 노드의 값이 바뀜에 따라 해당 index를 포함하고 있는 쿼리를 전부 업데이트 해주어야 한다. 느낌 자체는 구간 곱 쿼리의 처리 방법과 비슷하게 해주면 된다. https://viyoung.tistory.com/248 [백준 11505번] [세그먼트 트리] 구간 곱 구하기 Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parame..

Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parameter로 주입한 value값을 토대로 갱신만 해주면 된다. 구간 곱의 경우는 0의 존재때문에 다시 갱신해주는 것이 편하다. 잘 생각해보면 update를 할 때, 변한 index를 포함하지 않는 부분은 기존 seg값을 재활용하고 포함하는 경우만 갱신해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; ll seg[4000000]; ll update(int node..

Approach 쿼리에 대한 업데이트가 자주 일어나고, 구간합을 구하는 상황이므로 세그먼트 트리를 활용해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; ll seg[4000000]; void update(int node_index, int node_left, int node_right, int index, ll value){ if(index < node_left || node_right < index) return; // Out of Bound seg[node_index] += value; if(node_left ==..

Approach "dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만 이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다. 따라서 이 문제는 dp로 풀 수 없다. 업데이트가 자주되고 특정 숫자까지 사용하였을 때 개수가 중요하므로 구간합과 쿼리로 문제 상황을 이해할 수 있다. 해당하는 숫자까지 사용했을 때의 개수가 주어진 숫자보다 더 큰 것 중 가장 작은 것을 찾아야 하는 상황이다. 특정 임계점을 기준으로 해당 경향성이 갈리므로 이분탐색을 활용해주면 된다. 따라서 시간 복잡도는, 이분탐색에서 logN이고 세그먼트에서 탐색이 logN, 마지막으로 모든 숫자에 대해 해당 작업을 처리해야하므로 N을 곱해서 $O(N(lgN)^2)$이다. C..

Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초과하게 된다. 이때 등장하는 방법이 Euler tour technique이다. 해당 방법을 통해 트리를 Array로 필 수 있게 된다. 기존에 진행하던 DFS 과정을 잘 생각해보면, 일종의 재귀적으로 계속해서 해당 노드를 기준으로 밑으로 내려가게 된다. 즉, DFS에서 방문순서를 기준으로 index를 부여할 수 있게 된다. 이를 바탕으로 다음과 같은 식을 잡을 수 있다. dfs_in[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 시작 index dfs_out[i] : 노드 i를 포함한 i의 subt..

Approach 특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다. 이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다. 따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다. 단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다. 처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만..

Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..