본문 바로가기
해피 코딩/알고리즘

[백준 10986] '나머지 합' 가장 쉽게 이해하기 JAVA

by happy-coding 2024. 12. 21.

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개의 경우를 찾기 위해, 합 배열 SM(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
  }
}

 

나머지 합 마무리 ✍️

이번 문제는 누적 합조합을 활용한 문제로, 다소 난이도가 있는 편입니다.
하지만 이해하기 어려운 문제도 시각적 자료를 통해 문제의 핵심을 분석하며 차근차근 해결해 보았습니다.

 

읽어주셔서 감사합니다 ☺️