목록구간합 (7)
Dev.baelanche
[백준 16713] Generic Queries
처음엔 문제 해석이 잘 안됐는데, 구간합을 합 대신 XOR로 구현하고 출력시에도 XOR하여 나타내면 된다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int pxor[] = new int[n+1]; st = new Strin..
[백준 16507] 어두운 건 무서워
2차원 배열 구간합을 구현하면 된다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int psum[][] = new int[r+1][c+1]; for(..
[백준 10211] Maximum Subarray
1차원 구간합 배열을 만들어 완전탐색으로 매 구간합의 최대값을 구한다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); while(t-->0) { int n = Integer.parseInt(br.readLine()); int psum[] = new int[n+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=0; i
[백준 11969] Breed Counting
번역 역시나 발번역이다. 구간합을 저장할 배열을 만들어 품종별로 소의 개수를 따로 세어주면 된다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int a[][] = new int[n][3]; int psum[][] = new int[..
[백준 11441] 합 구하기
11659번 문제와 완전히 유사한 구간합 문제이다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int a[] = new int[n]; int psum[] = new int[n+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=0; i
[백준 11660] 구간 합 구하기 5
이차원 배열의 구간합이다. 예제의 구간합 배열은 다음과 같다. 1 3 6 10 3 8 15 24 6 15 27 42 10 24 42 64 사각형 넓이 구할때와 마찬가지로 부분합 C = (A+B) + (A+B) - A = A + 2B 이다. 위 식대로 하면 표대로 배열의 값을 채워 넣을 수 있고 구간별 합을 구할때도 위 식을 활용한다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); i..
[백준 11659] 구간 합 구하기 4
구간합 문제이다. 입력받은 배열 + 이전 배열을 더한 값을 저장하는 배열을 만들어 출력한다. a[] 5 4 3 2 1 psum[] 0 5 9 12 14 15 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int a[] = new int..