[BOJ] 10986. 나머지 합 (Java / Python)

백준 10986: 나머지 합 (자바/파이썬)

10986번: 나머지 합

이걸.. 내가 풀었다고 해도 되나요?

 

1. 모듈러 연산 이용하기(A + B) % M = ((A % M) + (B % M)) % M

 

- 이 문제에서 찾아야 하는 것(A - B) % M = 0

 

- 그렇다면 이용해야 하는 것(A % M) - (B % M) = 0(A % M) = (B % M)

 

누적합의 나머지를 구한 후모듈러 연산을 이용할 수 있는, 즉 같은 나머지를 가진 2개 이상을 찾으면 됨

 

자바

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

public class B10986 {
    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 ans = 0;	// 여기에도 int 쓰면 안됨

        st = new StringTokenizer(br.readLine());

        long[] arr = new long[N];
        arr[0] = Integer.parseInt(st.nextToken()) % M;
        if (arr[0] == 0) ans++;

        long[] cnt = new long[M];

        for (int i = 1; i < N; i++) {
            long n = (arr[i - 1] + Integer.parseInt(st.nextToken())) % M;
            arr[i] = n;
            if (n == 0) ans++;
        }

        for (long a : arr) {
            cnt[(int)a]++;
        }


        for (long c : cnt) {
        	// 2로 나누는 이유는 어차피 nC2니깐
            // 분자도 n * n-1 까지만 하면 됨
            if (c >= 2) ans += c * (c - 1) / 2;
        }


        System.out.println(ans);
    }
}

 

파이썬

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = list(map(int, input().split()))
ans = 0

L[0] = L[0] % M
if L[0] == 0:
    ans += 1

for i in range(1, N):
    L[i] = (L[i - 1] + L[i]) % M
    if L[i] == 0:
        ans += 1


cnt = {}
for i in range(N):
    if L[i] in cnt:
        cnt[L[i]] += 1
    else:
        cnt[L[i]] = 1

for c in cnt:
    if cnt[c] >= 2:
        ans += (cnt[c] * (cnt[c] - 1)) // 2

print(ans)

자바에서는 long을 안 쓰면 에러가 나지만, 파이썬에서는 모듈러 연산을 마치고 나머지의 수를 셀 때(cnt) 딕셔너리가 아닌 리스트를 쓰면 인덱스에러로 틀림

N과 M의 범위에 주의