구간 합
-
이번 문제도 합 배열을 이용해 해결해야 하는 문제이다. 합 배열을 구하는 방법은 S[i] = S[i-1] + A[i] 이다. 위 예제를 기준으로 살펴보자. 합 배열은 [1, 3, 6, 7, 9]로 3으로 나눈 나머지의 배열은 [1, 0, 0, 1, 0]이다. S[i] % M = 0이고 S[j] % M = 0이면 (S[i] - S[j]) % M = 0 이다. 따라서 S[i] % M == S[j] % M인 i와 j를 찾으면 되므로 나머지 배열의 같은 값을 가진 인덱스 중에서 2개를 고른 뒤 정답에 추가해 주면 된다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOEx..
[백준] 구간 합 - 10986_나머지 합 구하기 Java[자바]이번 문제도 합 배열을 이용해 해결해야 하는 문제이다. 합 배열을 구하는 방법은 S[i] = S[i-1] + A[i] 이다. 위 예제를 기준으로 살펴보자. 합 배열은 [1, 3, 6, 7, 9]로 3으로 나눈 나머지의 배열은 [1, 0, 0, 1, 0]이다. S[i] % M = 0이고 S[j] % M = 0이면 (S[i] - S[j]) % M = 0 이다. 따라서 S[i] % M == S[j] % M인 i와 j를 찾으면 되므로 나머지 배열의 같은 값을 가진 인덱스 중에서 2개를 고른 뒤 정답에 추가해 주면 된다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOEx..
2024.01.31 -
바로 전 문제와 마찬가지로 구간합을 이용하면 풀 수 있는 문제이다. 다만, 구간 합을 구하는 방법이 전과는 달라졌다. 먼저 A[2,2] 까지의 합을 구하는 방법을 생각해보면 S[1,2] + S[2,1] - S[1,1] + A[2,2]로 나타낼 수 있다. 이것으로 보아 합 배열을 나타내는 표현식은 S[i,j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j] 이다. 위에 나온 예제를 활용하여 [2,2]부터 [3,4]까지의 합을 구해보면 S[3,4] - S[3,1] - S[1, 4] + S[1, 1]으로 표현이 가능하다. 이제 공식으로 변환을 하면 [x1, y1] 부터 [x2, y2] 까지의 합은 S[x2, y2] - S[x2, y1-1] - S[x1-1, ..
[백준] 구간 합 - 11660_구간 합 구하기 Java[자바]바로 전 문제와 마찬가지로 구간합을 이용하면 풀 수 있는 문제이다. 다만, 구간 합을 구하는 방법이 전과는 달라졌다. 먼저 A[2,2] 까지의 합을 구하는 방법을 생각해보면 S[1,2] + S[2,1] - S[1,1] + A[2,2]로 나타낼 수 있다. 이것으로 보아 합 배열을 나타내는 표현식은 S[i,j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j] 이다. 위에 나온 예제를 활용하여 [2,2]부터 [3,4]까지의 합을 구해보면 S[3,4] - S[3,1] - S[1, 4] + S[1, 1]으로 표현이 가능하다. 이제 공식으로 변환을 하면 [x1, y1] 부터 [x2, y2] 까지의 합은 S[x2, y2] - S[x2, y1-1] - S[x1-1, ..
2024.01.31