https://www.acmicpc.net/problem/10986
주의❗
이 문제를 해결하려면 먼저 '누적 합' 개념을 이해해야 합니다.
이 글은 누적 합의 개념을 알고 있다는 가정을 바탕으로 작성되었습니다. 😊
문제
출력
분류
핵심 분석 ✅
문제를 풀기 전에, 시각적 자료를 활용하여 문제의 핵심 분석해 보겠습니다.
문제만 보면 다소 이해하기 어려울 수 있으니, 그림과 함께 살펴보며 이해해 보겠습니다.
보다 쉬운 설명을 위해 문제의 예제 입력값을 참고하여 분석하도록 하겠습니다.
예제 입력
5 3
1 2 3 1 2
그림을 활용해 연속된 부분의 합 (Ai + ... + Aj) 이 M(3) 으로 나누어떨어지는 구간의 개수를 구해보았습니다.
누적 합 S 배열 구하기
먼저, 합 배열 S를 구한 뒤, S배열에서 M(3) 으로 나누어떨어지는 구간의 개수를 계산해 보겠습니다.
그림을 참고하면, 총 3개 경우의 수를 확인할 수 있습니다.
앞서 그림에서 확인했던 7가지 경우의 수 중, 이번에 구한 3개의 경우의 수는 다음과 같습니다.
변경된 합 배열 S 구하기
7가지 경우의 수 중 남은 4개의 경우를 찾기 위해, 합 배열 S를 M(3)으로 나눈 변경된 합 배열 S를 구해 보겠습니다.
변경된 합 배열 S를 사용하여 남은 경우의 수 구하기
변경된 합 배열 S를 활용하여, 배열 A[1]+ ... +A[3] 구간까지의 값을 계산해 보겠습니다.
구간 합 A[i]+ ... +A[j] 을 구하는 공식은 다음과 같습니다 🔍
- S[j]−S[i−1]
그림에서 i의 인덱스는 1, j의 인덱스는 3이므로, 위 공식에 값을 대입하면 다음과 같이 계산됩니다.
- S[3]−S[0] = A[1] + A[2] + A[3]
다시 문제로 돌아와, 우리는 연속된 부분의 합 (A[i]+ ... +A[j]) 이 M(3) 으로 나누어떨어지는 구간의 개수를 구해야 합니다.따라서,
- ( S[3]−S[0] ) % 3=0 ➡️ ( 1 - 1 ) % 3 = 0 이라는 것을 알 수 있습니다.
위와 같은 방식을 사용하면, 나머지 3개의 경우도 동일한 방법으로 구할 수 있습니다.
경우의 수 구하기
문제를 살펴보면, 우리는 경우의 수만 구하면 됩니다. 이를 위해 조합을 활용해 경우의 수를 계산할 수 있습니다.
변경된 합 배열 S에서
- '0'의 개수는 3개이므로 ➡️ 3C2 를 계산하여 3개의 경우가 나옵니다.
- '1'의 개수는 2개이므로 ➡️ 2C2 를 계산하여 1개의 경우가 나옵니다.
따라서 총 경우의 수는
- 3+3+1=7
이를 통해 총 7가지 경우가 나온다는 것을 알 수 있습니다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 5
int M = Integer.parseInt(st.nextToken()); // 3
long[] S = new long[N];
long[] C = new long[M];
st = new StringTokenizer(br.readLine()); // 1 2 3 1 2
// 누적 합 S
S[0] = Integer.parseInt(st.nextToken());
for (int i= 1; i < N; i++){
S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
}
long result = 0;
// 변경된 합 배열 S
for (int i = 0; i < N; i++) {
int remainder = (int)(S[i] % M);
if (remainder == 0){
result ++;
}
C[remainder] ++; // 조합에서 사용 할 0과 1의 개수 카운트
}
// 조합 공식
for (int i = 0; i < M; i++) {
if (C[i] > 1) {
result += (C[i] * (C[i] - 1))
}
}
System.out.println(result);
}
}
코드 풀이
1️⃣ 합 배열 S와 조합 계산에서 사용할 '0' 과 '1' 의 개수를 카운트하기 위한 배열 C를 정의합니다.
long[] S = new long[N];
long[] C = new long[M];
2️⃣ if 문을 사용하여 합 배열 S에서 으로 나누어떨어지는 구간의 개수를 확인하고, 각 경우에 대해 result++ 연산을 통해 결과를 누적합니다.
3️⃣ C[remainder]++ 를 사용하여 변경된 합 배열에서 나머지가 '0' 또는 '1' 인 값의 개수를 카운트합니다.
for (int i = 0; i < N; i++) {
int remainder = (int)(S[i] % M); // 누적 합 %3
if (remainder == 0){
result ++;
}
C[remainder] ++; // 조합에서 사용 할 0과 1의 개수
}
4️⃣ 조합 공식을 사용하여, 남은 i, j 쌍의 개수를 계산합니다.
변경된 합 배열 S에서
- '0'의 개수는 3개이므로 ➡️ 3C2 를 계산하여 3개의 경우가 나옵니다.
- '1'의 개수는 2개이므로 ➡️ 2C2 를 계산하여 1개의 경우가 나옵니다.
- 조합 공식에서 3C2는 ➡️ 3P2 / 2 와 같으므로, 아래와 같은 식으로 계산할 수 있습니다.
for (int i = 0; i < M; i++) {
if (C[i] > 1) { // 2장을 뽑기 때문
result += (C[i] * (C[i] - 1)) / 2; // 3P2 / 2
}
}
나머지 합 마무리 ✍️
이번 문제는 누적 합과 조합을 활용한 문제로, 다소 난이도가 있는 편입니다.
하지만 이해하기 어려운 문제도 시각적 자료를 통해 문제의 핵심을 분석하며 차근차근 해결해 보았습니다.
읽어주셔서 감사합니다 ☺️
'해피 코딩 > 알고리즘' 카테고리의 다른 글
[이론] 유니온 파인드 너무 쉬운데? (5) | 2024.12.24 |
---|---|
[백준 1934] 문제로 이해하는 유클리드 호제법 JAVA (2) | 2024.12.16 |
[백준 1929] 문제로 이해하는 에라토스테니스의 체 JAVA (0) | 2024.12.16 |
[이론] 병합 정렬 알고가기 (0) | 2024.12.12 |
[이론] 버블 정렬 알고가기 (3) | 2024.12.05 |