728x90
320x100
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
📌 접근 방법
- 처음에 구간합을 이용해서 풀기는 풀었는데 시간초과가 났다..
- 아무래도 이중 배열을 사용해서 시간초과가 난 듯 하다(?)... (시간 제한이 1초임)
⚡️ 시간 초과 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
int N, M, cnt = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int arr[] = new int[N+1];
for(int i=1; i<=N; i++) {
arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
}
for(int i=1; i<=N; i++) {
for (int j=i; j<=N; j++) {
if(((arr[j] - arr[i-1]) % 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);
}
}
시간 제한이 없었더라면 간단하게 풀 수 있었을 거 같은데,, 중첩 반복문이 연산 시간이 오래 걸려서 안된듯합니다...
많이 많이 어려웠습니다......
![](https://t1.daumcdn.net/keditor/emoticon/friends1/large/022.gif)
💡 Reference
[Java / 백준 10986] 나머지 합
백준 10986 문제는 구간 합을 응용한 심화 문제입니다. 여러 시행 착오를 겪으면서 문제를 해결한 내용을 요약 정리했습니다😅
velog.io
728x90
반응형
'Coding Test > Baekjoon' 카테고리의 다른 글
[JAVA][Baekjoon] 1940번 주몽 ⭐️ (1) | 2024.03.23 |
---|---|
[JAVA][Baekjoon] 2018번 수들의 합 5 🌟 (0) | 2024.03.23 |
[JAVA][Baekjoon] 11660번 구간 합 구하기 5 (1) | 2024.03.11 |
[JAVA][Baekjoon] 11659번 구간 합 구하기 4 (0) | 2024.03.11 |
[JAVA][Baekjoon] 1546번 평균 (0) | 2024.03.02 |