1. 문제 링크 및 문제
https://www.acmicpc.net/problem/2015
2. 해결 방법 생각해보자 ...
누적합을 활용하는 문제였는데, N과 K의 범위가 어마어마하다!
❌ 처음에 2중 반복문을 돌려 sumArr[i] == K + sumArr[i-j] 인 값을 구했으나 시간 초과!
⭕️ 맵 자료구조를 사용
맵(key,value)
=> 맵 현재값 없으면? (누적합 값, 1 )
있으면? (누적합 값 , 현재값+1 )
이렇게 사용하는 이유는!
범위가 크므로 반복문을 돌리지 않고, 앞에서 나온 누적합들을 맵의 키에 기록해뒀다가
맵 키 중에 (현재누적합 - K ) 가 있냐? 그럼 ( answer += 그 값의 value ) 를 하기 위해서이다.
💡 그럼 ( 현재 누적합 -K ) 라는 식은 어디서 나온 것이냐?
우리가 문제에서 구해야 하는 값은 K 이다.
누적합을 사용해서 문제를 풀려면 (sumArr[i]-sumArr[i-j] = K ) 를 만족하는 경우의 수를 구하면 된다. ( 누적합 공식입니다 )
즉, 현재값 - 앞의 누적합들 중 하나 = K 이면 문제 조건 만족이라는 말인데
여기서 K 와 누적합들 중 하나를 앞뒤로 바꾸면
현재값 - K = 앞의 누적합들 중 하나 라는 다른 형태로도 표현할 수 있다.
그래서 반복문을 돌릴 필요 없이, Map 에 앞의 누적합들을 기록해뒀다 값이 들어올 때 마다, map의 키 중에 (현재값-K) 가 있냐? 그럼 그 value 더할게! 를 해주면 된다.
예시로 이해해보자
이 예제의 누적합을 구하면
sumArr = 0 , 1+2 , 1+2+3 , 1+2+3+4 , 1+2+3+4+5 , 1+2+3+4+5+0
즉 sumArr = 0 1 3 6 10 15 15 이다.
여기서 K=5 를 만족하는 경우의 수를 구하려면
우리는 sumArr[1] 일 때 : sumArr[1]-sumArr[0]
sumArr[2] 일 때 : sumArr[2]-sumArr[1] , sumArr[2]-sumArr[0]
sumArr[3] 일 때 : sumArr[3]-sumArr[2] , sumArr[3]-sumArr[1] , sumArr[3]-sumArr[0]
즉 이렇게 앞의 누적합들이랑 비교를 해서 구해야한다.
값을 대입해서 보면 이해하기 쉬울 것이다
sumArr[1] 일 때 : 1-0
sumArr[2] 일 때 : 3-1, 3-0
sumArr[3] 일 때 : 6-3, 6-1, 6-0
이런 식으로 5 가 나오는 경우의 수를 구하면 되는데 예제 케이스가 많아질수록 반복문이 깊어지므로
반대로 생각해서 sumArr[현재값]-K 가 누적합들 리스트 중에 있냐 ? 로 계산한다는 것이다.
sumArr[1] 일 때 , 1 이므로 1-5 가 map 에 있냐?
없다. map(1,1) 추가해줌.
sumArr[2] 일 때, 3 이므로 3-5 가 map 에 있냐?
없다. map(3,1) 추가해줌.
sumArr[3] 일 때, 6 이므로 6-5 가 map 에 있냐?
있다 ! 그럼 map(1) 의 value 값을 가져와 정답에 더해준다. answer += (map.get(1) + 1)
그리고, map(6,1) 추가해줌.
sumArr[4] 일 때, 10 이므로 10-5 가 map 에 있냐?
없다. map(10,1) 추가해줌.
sumArr[5] 일 때 ,15 이므로 15-5 가 map 에 있냐?
있다! 그럼 map(10)의 value값을 가져와 정답에 더해준다. answer +=(map.get(10) +1 )
그리고, map(15,1) 추가해줌.
sumArr[6] 일 때, 15 이므로 15-5 가 map 에 있냐?
있다! 그럼 map(15-5)의 value값을 가져와 정답에 더해준다.
그리고 , map(15) 가 이미 있으므로 + 1 = map(15,2) 추가해줌.
그럼 최종적으로 answer 가 나온다 ~~
3. 코드
import java.io.*;
import java.util.*;
public class Main{
static int N,K ;
static int[] sumArr;
static long count = 0 ;
public static int stoi(String str){
return Integer.parseInt(str);
}
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi(st.nextToken());
K = stoi(st.nextToken());
sumArr = new int[N+1];
HashMap<Integer,Long> map = new HashMap<>(); // 누적합의 수와 갯수를 저장할 map
st = new StringTokenizer(br.readLine());
for(int i=1;i<N+1;i++){
sumArr[i] = sumArr[i-1] + stoi(st.nextToken()); // 누적합
if(sumArr[i] == K ) count ++ ; // 현재합이 K 인 경우 +1
// 현재누적합 - K 값이 map 에 있냐?
if(map.containsKey(sumArr[i]-K)) count += map.get(sumArr[i]-K);
// 현재 누적합값 map 에 추가
if(!map.containsKey(sumArr[i])) map.put(sumArr[i],1L);
else map.put(sumArr[i], map.get(sumArr[i])+1);
}
System.out.println(count);
}
}