백준 10986 나머지 합 [JAVA]

문제 해석

• 문제 설명에 앞서 누적합을 간단하게 정리하고자 한다.(이미, 누적합 문제를 몇개 풀었지만 정리한 기억이 없어서...)
  
• 앞서 설명한대로 1부터 x까지, 즉 전체의 누적합을 코드로 변환하면 아래와 같이 설명할 수 있다.

  
  int[] preSum = new int[x]; //누적합을 구할 배열
  int[] number = new int[x]; //입력받은 숫자  

  for(int i = 1; i <= x; i++){
      sum += arr[i-1] + number[i]
  }
                     

• 그렇다면 구간합은 어떻게 구할까?
• 만약 a ~ b-1의 구간합을 구하고 싶다면 아래와 같이 표현할 수 있다.

int[] sum = new int[x+1];
for (int i = 0; i < x; i++) {
    answer[i] = arr[b] - arr[a-1];
}

• 이제 다시 문제로 돌아오면 "연속된 구간이 주어진 값에 의해 나누어 떨어지는"을 생각해보자.
• 일단 구간이 [a, b]인 값을 구하고자 한다면 위에서도 설명했듯이 [1, b] - [1, a-1]을 해주면 된다.
  

• 즉, %M한 값이 같은 구간으로 나누어서 구하면 된다.
• 예를 들어 M이 3이라고 할때 나머지로 나올 수 있는 것은 0, 1, 2 가 된다.
  
• 나머지의 값으로 나오는 구간별 값은 각가 아래와 같이 나눌 수 있다.
  
• 단순누적합에서 나온 결과 값으로 2개를 뽑아 [1, b] - [1, a-1] 와 같이 계산했을 때 조합을 M으로 나누었을때 0이 나오는 개수를 구한다.
• 조합 개수를 모두 구했다면 단순누적합을 더하면 최종 값이 나오게 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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()); //나누는 수

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

        int[] count;
        //입력과 동시에 누적합 구하기
        count = new int[M]; //나머지 종류별로

        int sum = 0; //누적합
        for(int i = 0; i < N; i++){
            int number = Integer.parseInt(st.nextToken());
            sum = (sum+num)%number; //누적합하여 M으로 나눈 나머지(인덱스 값이 됨)
            count[sum]++;
        }

        long cnt = count[0]; //자기 스스로 나머지가 0이 나오는 경우
        for(int i = 0; i < count.length; i++){
            //조합으로 나머지가 0이 나오는 경우
           cnt += (long)count[i] * (count[i]-1)/2; //10^6 * 10^6임으로 overflow 방지로 long형으로
        }

        System.out.println(cnt);
    }

}

결과

느낀 점

이해하는 데 진짜 오래걸린 문제이다. 일단 처음 시작자체를 못해서 다른 분들의 아이디어를 참고했는데 참고해도 이해를 못해서 꽤 걸렸던 문제이다.
다행히 문제를 보면 볼수록 서서히 이해가 되어서 풀 수 있었다.