Java 백준 문제풀이 (39) 10986 : 나머지 합

 

 

첫 번째로 어떻게 풀어야하는지 전혀 감이 안 왔고,

어떻게 풀어야하는지 알게된 후로는 어떻게 구현해야할지 감이 안 왔다..

그리고 기껏 풀었더니 그 뒤에는 범위 때문에 에러나서 또 한 시간 날림.. ㅎㅎ 내 피같은 시간...

 

일단 예제를 손으로 써서 어떻게 7이 출력되는 것인지 무식한 방법으로 확인해보자.

똑똑한 사람들은 이 글 읽지 마시오. 부끄러우니까요.

 

 

 

 

 

 

 

 

1 2 3 1 2의 누적합은 1 3 6 7 6이고 이를 3으로 mod연산하면 1 0 0 1 0이 된다.

우선 각 부분합의 결과가 0인 경우는 모두 정답에 포함되기 때문에 이미 3개 구했다.

 

구간합을 구하는 공식은 sum[j] - sum[i]인데,

 

https://7357.tistory.com/229?category=1066252 

백준 문제풀이 (38) 11659, 11660 : 구간합구하기4,5



(sum[j] - sum[i]) % M = 0인 경우를 모두 구해야 한다.

이는 (sum[j]%M) - (sum[i]%M) = 0과 같으며, 양변에 같은 값을 더하면 sum[j]%M = sum[i]%M라는 공식을 얻을 수 있다.

 

그렇다.. 방금 전까지 어려운 문제였는데 갑자기 조합 구하는 공식만 알면 손쉽게 풀 수 있는 문제가 된 것이다.

xCy를 구하는 공식은 x * (x-1) / y!인데, 우리는 2개의 숫자 쌍만 구하면 되기 때문에 뒤는 2로 고정이다.

 

즉, 합연산하면서 나오는 값의 개수를 체크해놓고 각 수에 대해 x * (x-1) / 2의 연산을 수행해서 모두 더해주면 끝.

나만 이렇게 어려웠나..? ㅎ

 

여기까지 봤으면 스스로 풀자.

정답은 밑으로~

 

참고로 문제 입력값 범위 때문에 기껏 다 풀었는데 수정하느라 열 받을 수 있다. 주의하자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        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()," ");
        long[] arr = new long[N+1];
        long[] count = new long[M];
        long sum = 0;
 
        for (int i=1; i<=N; i++) {
            long input = Long.parseLong(st.nextToken());
 
            sum = input + arr[i-1];
            arr[i] = sum;
 
            count[(int) (arr[i]%M)]++;
        }
 
        long answer = count[0];
        for (int i=0; i< count.length; i++) {
            answer += count[i] * (count[i] - 1) / 2;
        }
 
        System.out.println(answer);
    }
}

 

 

가장 오래 걸리는 알고리즘이 N의 원소를 가진 반복문이므로 이 풀이 방법의 시간 복잡도는 O(N)이다.