풀이 펜윅 트리로 검색해서 들어갔던 문제이기 때문에 어떻게든 펜윅 트리를 사용해서 풀어야 한다는 강박관념이 있었던 문제였습니다. 펜윅트리는 저번 포스팅에서도 간략하게 설명했지만 구간합을 빠르게 구하기 위해 사용되는 알고리즘입니다. 따라서 문제의 핵심은 특정 영화의 앞에 놓여있는 영화의 개수를 어떻게 구간합으로 표현할 것인가?입니다. 1. 영화는 한번의 시행때마다 그 위치가 움직이므로 위치의 변동을 표현할 수 있어야 한다. 2. 펜윅 트리는 구간의 합을 빠르게 구할 수 있는 자료구조이므로, 구간의 합을 영화 앞에 쌓여 있는 영화의 개수로 치환할 수 있어야 한다. 3. 영화의 위치가 변했을 때, 트리를 업데이트하기가 용이해야 한다. 위 생각을 적용해볼 때, n+m의 크기를 갖는 펜윅 트리를 구성하고, 특정 ..

풀이 구간 합을 구하기 위해서 펜윅 트리를 사용하였습니다. 펜윅 트리에 대한 자세한 내용은 펜윅트리 포스팅을 참고해주세요 소스 코드 (JAVA) import java.util.*; public class BOJ_2042 { public static void main(String args[]){ Scanner input = new Scanner(System.in); int n = input.nextInt(); int m = input.nextInt(); int k = input.nextInt(); long[] matrix = new long[n+1]; FenwickTree fenwick = new FenwickTree(n); // initialize fenwick tree for(int i=1;i