백준 [자바 java] 10986 : 나머지 합

문제설명

연속된 수열이 있을 때 이 수열의 부분합이 특정 수로 나누어 떨어지는 경우의 수를 구하여라

 

풀이

처음에는 b로 나누어떨어지는 덩어리를 구해서 이어지는 경우의 수를 구하는 방식으로 문제를 풀었지만 시간초과가 났다.

그래서 다른 사람의 풀이를 봤는데 수학적인 부분을 사용해서 풀어야하는 문제임을 깨달았다.

난 이런 쪽으로 좀 약한 것 같다...

 

일단 부분합을 구하는 것까지는 생각했다.

12312배열이 있고, 3으로 나누어떨어지는 부분배열의 수를 구해야한다고 했을 때

주어진배열	1	2	3	1	2
합배열	1	3	6	7	9
합 나머지배열	1	0	0	1	0

 

위와 같이 배열을 만든다.

우리가 a에서 b까지의 부분합이 m으로 떨어지느냐를 알려면

(합배열[b] - 합배열[a]) % m = 0 인지를 보면 된다. 기존 나의 방식은 이와 같았고, 시간초과가 났다.

 

그럼 어떻게 해야하느냐..

 

합배열[b]%m - 합배열[a]%m = 0

합배열[b]%m = 합배열[a]%m

을 이용해야한다. 즉, 합 나머지배열이 같은 경우의 수를 구하고, 이 수에 대해서 각각 combination을 하면 된다.

 

for(int i = 1;i<=a;i++){
      sum[i] = ((sum[i-1] + Integer.parseInt(st.nextToken())) % b);
      num[(int)sum[i]]+=1;
    }

따라서 이와 같이 num 배열에 각 인덱스 별 합 나머지 배열의 수를 저장하고,

 

long ans = num[0];

for(int i = 0;i<=b;i++){
  long k = num[i];
  ans += (k)*(k-1)/2;
}

이와 같이 combination을 해주었다.

이 때 num[0]에 있는 수들은 처음부터 n까지의 합이 m으로 나누어떨어지는 경우이므로 단독으로도 m으로 나누어 떨어지는 배열이 되므로, 미리 더해줬다.

 

package org.example;
import java.util.*;
import java.io.*;

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 a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

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

    long[] sum = new long[a+1];
    long[] num = new long[b+1];

    for(int i = 1;i<=a;i++){
      sum[i] = ((sum[i-1] + Integer.parseInt(st.nextToken())) % b);
      num[(int)sum[i]]+=1;
    }

    long ans = num[0];

    for(int i = 0;i<=b;i++){
      long k = num[i];
      ans += (k)*(k-1)/2;
    }
    System.out.println(ans);
  }
}

전체 코드는 위와 같다.