백준 10986 java - 나머지 합(누적합, feat. 골드1달성)

문제, 입출력, 테스트케이스

해당 문제는 거의 하루 반나절을 고민했는데 결국 질문 검색의 힌트 + 굇수분들의 도움을 받아 푼 문제다.

누적합 + 수학적 사고력 + 데이터 타입의 조합으로 골드3인데 골드3보다 높아보인다...

 

<문제 접근/풀이과정>
1. 일단 구간합이 필요하므로 누적합 필요함.
2. 단순히 누적합끼리 2중 for문을 돌리면 1,000,000 * 1,000,000 = 1초 초과됨 -> 다른 방법 필요
3. 나머지들의 누적합을 활용해보면 나머지가 같은 구간끼리 뺀다면 그게 나머지 0이 됨
4. 나머지 0의 경우 그 자체로도 답이 되고 서로 빼서 구간합 만든 것도 답이 되므로 카운팅할 때 신경 써야함
5. n*(n-1)/2 (nC2)을 구할 때 n이 1,000,000일 경우 int범위를 벗어나므로 long범위로 선언하여야 하며 누적합 배열을 int형으로 선언했으면 long으로 명시적 형변환을 하여야 오버플로우가 생기지 않음

package boj;

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

public class Boj_10986 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		int sumModuloGroup[] = new int[M];
		stz = new StringTokenizer(br.readLine());
		int acSum = 0;
		for (int i = 1; i <= N; i++) {
			acSum += Integer.parseInt(stz.nextToken());
			acSum %= M;
			sumModuloGroup[acSum]++;
		}
		long cnt = 0;
		for (int i = 0; i < M; i++) {
			cnt += (long)(sumModuloGroup[i]) * (sumModuloGroup[i]-1) /2;
		}
		cnt += sumModuloGroup[0];
		System.out.println(cnt);
		
	}
}

아무래도 수학적 사고력이 부족한 것 같다... 분발해야지!

아 그리고 드디어 골드 1을 달성했다. 물골드이지만 노력의 결실로 더욱 더 열심히 알고리즘 공부를 할 동기부여가 되었다!