[JAVA][Baekjoon] 10986번 나머지 합 ⭐️

10986번: 나머지 합

---

📌 접근 방법

• 처음에 구간합을 이용해서 풀기는 풀었는데 시간초과가 났다..
• 아무래도 이중 배열을 사용해서 시간초과가 난 듯 하다(?)...

 

 

⚡️ 시간 초과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
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 []arr = new long[N+1];
       st = new StringTokenizer(br.readLine());

       for(int i=1; i<=N; i++){
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }
       int cnt = 0;
       for(int i=1; i<=N; i++){
           for(int j=0; j<i; j++){
               if((arr[i]-arr[j])%M == 0 ){
                   cnt ++;
               }
           }
       }
       System.out.println(cnt);

   }
}

 

⚒️ 문제 분석

• (A + B) % C = ((A % C) + (B % C)) % C 이 공식을 기억!
  • 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다는 것을 사용
• S[i] % M = S[j] % M 이라면 (S[j] - S[i]) % M = 0이라는 결과가 나옴
• 즉, 구간합 배열의 원소를 M으로 나눈 나머지로 배열을 업데이트한 후 S[j] 와 S[i]가 같은 (i, j) 쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있음!

 

ex)

• 1, 2, 3, 1 2 를 입력 ➡️ 1, 3, 6, 7, 9 (구간합)
•  M = 3 ➡️ 1, 0, 0, 1, 0 (구간합 % M)
• 일단 0의 개수를 카운팅해줌 ➡️ 3
• 나머지 값이 같은 인덱스 수 카운팅 ➡️ 3(0으로 같음), 2 (1로 같음)
  
  • 원소 값이 같은 2 개의 원소를 뽑는 경우의 수를 구할것 ! 
  • 3C2, 2C2 => 3 + 1

➡️ 3 + 3 + 1 = 7

 

✅ PASS CODE

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

public class Main {
   public static void main(String [] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        long []arr = new long[N];

       arr[0]  = sc.nextInt();
       for(int i=1; i<N; i++){
            arr[i] = arr[i-1] + sc.nextInt();
        }
       long []C = new long[M];
       long cnt = 0;
       for(int i=0; i<N; i++){
           int tmp = (int) (arr[i] % M);
           if(tmp == 0 ) cnt ++;
           C[tmp] ++;
       }
       for (int i=0; i<M; i++){
           if(C[i]>1) {
               cnt += ((C[i] * (C[i]-1))/2);
           }
       }
       System.out.println(cnt);

   }
}

쪼금 어려웠습니다!!! 

 

728x90

SMALL