잡동사니_로드

Inversion Count (배열 내 i arr[j]의 경우의 수) 의 수를 구하는 문제이다. 위 3 2 1 경우를 보면 (3 2) (3 1) (2 1) 에만 발생한다. Merge Sort 중 병합 과정에서 두 번째 dataset의 데이터가 첫 번째의 것보다 작아 tmp 배열에 정렬될 때, 첫 번째 dataset에 남아 있는 data의 수만큼 inversion 경우의 수를 만들 수 있으므로, 이 상황 때마다 answer에 더해주면 된다. - ex) 5 4 / 3 7 merge 시, 5 > 3이므로 3이 먼저 tmp 배열에 들어간다. inversion 경우의 수는 (5 3) (4 3)이 발생하므로 이 때 2를 더해주자 import java.util.*;import java.io.*;public ..

cf > cout는 C++ 에서 출력을 의미한다 위 cout 이 실행될 때에는 정렬 완료된 다음 loop에서 발생한다. 이를 위해 각 loop 당 왼쪽으로는 1번씩 이동하는 걸 이용할 수 있다. 정렬 전/후 index를 비교해서 왼쪽으로 움직인 정도의 최댓값 + 1을 출력하자 (+1은 정렬이 제대로 되었는지 확인 후 출력 위한 loop) - ex) 10 1 5 2 3 1 5 2 3 10 import java.util.*;import java.io.*;public class Main { static int n; static int answer = Integer.MIN_VALUE; static List list = new ArrayList(); ..

Stack 내에 배열의 index 값을 넣어 풀었다. arr[peek] 만약 arr[peek] > arr[index] 인 경우 stack에 계속 push함으로써 처음 > pop() 에 들어있는 index의 값이 arr 기준 내림차순이 되도록 유지한다. ex) 아래 두 번째 줄 1 2의 경우 arr[1] : 5, arr[2] : 2로 내림차순을 유지하다가, arr[3] (7) 이 들어오려 할 때 하나씩 제거해간다 이러한 스택을 Monotone Stack이라 함 (특정 순서 유지하면서 데이터 관리) import java.util.*;import java.io.*;public class Main { static int n; static int [] arr; static int [..

Deque를 통해 해결 가능! NoSuchElement import java.util.*;import java.io.*;public class Main { static int n, l; static int [] arr; static Deque deque = new ArrayDeque(); public static void main (String [] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System..

합 배열을 만들고, 이중 반복문을 통해 해결하는 것은 시간을 초과하게 될 것 같다. 따라서 S[i] % m과 S[j] % m이 같을 때, (S[i] - S[j]) % m = 0임을 이용한다. 1 2 3 1 2 원본 배열 1 3 6 7 9 합 배열 1 0 0 1 0 (합 배열 대해 % m (위 예제에서는 3) 적용) - 이 때, 나머지 연산 결과가 0이라는 건 1st ~ i번째 요소까지의 합이 m으로 나누어 떨어지므로 그 수만큼 answer 증가 0이 3개, 1이 2개가 있으므로 3C2 + 2C2 = 4 따라서 답은 7입니다 cf> 10~11퍼에서 계속 틀렷는데 combination 부분에 (long) 을 넣었더니 풀렸다. import java.util.*;impor..

부분 합 문제이고, 데이터에 변화가 따로 없기에 부분 합 배열을 통해 해결했다. 당시 메모인데 상단 공식은 부분 합 배열을 채우는 공식, 하단은 범위 내 부분 합을 구하는 공식이다 import java.util.*;import java.io.*;public class Main { static int n, m; static int [][] arr; static int [][] sumArr; public static void main (String [] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWr..