BOJ_10986 : 나머지 합

👉 문제링크

10986번: 나머지 합

---

---

🔸 문제 분석 🔸

• n개의 입력되는 숫자의 부분 구간 합이 m으로 나누어 떨어지는 경우의 수를 출력한다.
• n은 100만, m은 100이다. 구간 합을 매번 계산하면 시간이 부족하므로 구간 합 배열을 미리 계산한다.
  • 구간 합 배열 공식 : S[i] = S[i-1] + A[i]
  • 배열에서 구간 합 구하기 ( i ~ j ) : S[j] - S[i-1]
  • 나머지도 미리 계산해 두는 것이 핵심 아이디어
    • (A + B) % C == ((A % C) + (B % C)) % C 이다.
    • S[i] % M == S[j] % M 이라고 하면, [S[i] - S[j]) % M 은 0이다.
    • 즉, 구간 합 배열 S의 값을 M으로 나눈 나머지로 업데이트하면, 값이 같은 인덱스 쌍은 M으로 나누어 떨어진다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        int m = Integer.parseInt(st.nextToken());
        long sum[] = new long[n+1];
        long c[] = new long[m];
        long answer = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++){ // 구간 합
            sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= n; i++){ // m으로 나누기
            int remainder = (int) (sum[i] % m);
            if (remainder == 0) answer++;
            c[remainder]++;
        }
        for (int i = 0; i < m; i++){ // 같은 나머지에서 2개의 인덱스를 선택하는 경우의 수
            if (c[i] > 1){
                answer += c[i] * (c[i]-1) / 2;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• 구간 합 배열 sum의 인덱스 1~n 까지 구간 합 값을 저장한다.
• 배열 sum을 순회하며 m으로 나눈 나머지를 계산한다.
  • 배열 c에 나머지를 인덱스로 해서 값을 증가시킨다. (배열 sum에서 같은 나머지를 같는 인덱스 수)
  • 나머지가 0이면 0~해당 인덱스까지의 구간 합이 m으로 나누어 떨어진다는 것이므로 answer을 증가시킨다.
    (인덱스 0~i의 구간 합은 공식으로 나타나지 않으므로 따로 계산해줘야 한다)
• 같은 나머지의 인덱스들에서 쌍을 만드는 경우의 수를 answer에 더한다.
  • C[i] 개에서 2개를 고르는 겨우의 수 : C[i] * (C[i] - 1) / 2

---

🔸 end 🔸

• 골드 3문제는 처음 풀어봤는데 상당히 어려운 것 같다. 교재를 보며 풀이를 보면서도 이해하는데 시간이 걸렸다.
• 구간 합 만으로도 이렇게 어려운 문제가 만들어지는게 신기하다.
• 구간 합으로 골드 3까지 풀어봤으니 어느정도 자신감이 생기는 것 같다.
• 기존의 내 풀이에서는 구간 합 배열을 구하고, 구간합에서 m의 나머지를 매번 계산하는 식으로 했는데 시간 초과가 났다.
  • 그 다음은 미리 나머지로 계산하고, 값이 같은 경우를 이중 반복문으로 찾는데 또 시간 초과가 났다.
  • 같은 나머지들의 수를 구하고, 2개를 만들 수 있는 경우의 수를 계산해야 했다.
• 그냥 풀이 자체도 구간 합에 미리 나머지를 계산한다는게 신기했는데, 나머지를 미리 세고 쌍을 만드는 조합의 수를 계산하는 건 생각도 못했다. 예전에 배운 수학 공식인데 참 낯설다...