[백준] 10986_나머지 합 - JAVA

나머지 합

이 문제도 구간 합 배열을 이용해야 한다. 구간 합 배열의 설명은 아래 링크로 이동하면 볼 수 있다.

[백준] 11659_구간 합 구하기4 - JAVA

 

배열의 연속 구간의 합을 구하려면 (A+B) % C로 구할 수 있다. 예제를 참고해서 풀어보자. 예제의 배열 {1, 2, 3, 1, 2} 중에 2와 3의 값을 대입해 보자. (2+3) % 3은 2이다. 또, 모듈러 연산은 분배법칙이 가능하다. 그러므로 ((2 % 3) + (3 % 3)) % 3과 같다.

즉, 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 구간 합의 나머지 연산을 한 값은 동일하다.

• 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값
  • 배열 : {1, 2, 3, 1}
  • 나머지 배열 : {1, 2, 0, 1}
  • 나머지 배열 더한 값 : 4
  • 나머지 연산 : 4 % 3 = 1
• 구간 합의 나머지 연산
  • 배열 : {1, 2, 3, 1}
  • 구간 합 배열 : {1, 3, 6, 7}
  • 구간 합의 나머지 연산 : 7 % 3 = 1

구간 합 배열을 이용한 식 S[j] - S[i]는 원본 배열의 j + 1부터 i까지의 구간 합이다. S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉, S[i] % M == S[j] % M인 개수를 구하면 된다.

다만 주의할 점은 S[i] % M == 0인 값은 따로 구해줘야 한다.

 

백준_10986

채점 현황

 

코드

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 {
        long answer = 0L;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int len = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] sumArr = new int[m];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < len; i++) {
            sum = (sum + Integer.parseInt(st.nextToken())) % m;
            sumArr[sum]++;
        }

        answer = sumArr[0];
        for(int i = 0; i < m; i++) {
            answer += (long) sumArr[i] * (sumArr[i] - 1) / 2;
        }
        System.out.println(answer);
    }
}

 

처음에 answer 변수의 타입을 'int'로 했다가 틀렸습니다! 를 받았다. 너무 기뻐하면서 말하는 거 아니냐고...

int가 왜 문제지 싶었는데 문제 입력 부분에 2번째 줄에 N개의 수를 109까지 받을 수 있어 answer += (int) sumArr[i] * (sumArr[i] - 1) / 2; 이 부분에서 에러가 나는 듯싶었다. 테스트 케이스도 제공된 게 없고.. 틀린 내용조차 모르겠어서 한참을 헤매다가 answer의 타입과 int 형변환을 long으로 변경해 주니 통과했다.

 

제출 결과