백준 복습 - 누적 합

누적 합 - 11659번: 구간 합 구하기 4

https://jh4995.tistory.com/202

[C] 백준 - 11659번: 구간 합 구하기 4

---

누적 합 - 2559번: 수열

https://jh4995.tistory.com/205

---

누적 합 - 16139번: 인간-컴퓨터 상호작용

https://jh4995.tistory.com/209

[C] 백준 - 16139번: 인간-컴퓨터 상호작용

---

누적 합 - 11660번: 구간 합 구하기 5

https://jh4995.tistory.com/207

[C] 백준 - 11660번: 구간 합 구하기 5

---

누적 합의 경우

누적 합을 구해놓으면 자연스럽게 원하는 구간의 합도 간단하게 구할 수 있다는 것을 이해해야한다

 

 

for (int k = 1; k < N + 1; k++)
	{
		scanf("%d", &num[k]);
		sum[k] = sum[k - 1] + num[k];
	}

위의 코드는 "11659번: 구간 합 구하기4" 문제의 풀이 중 일부이다

num배열에 N개의 숫자들을 입력받은 뒤,

다시 sum배열에 해당 숫자를 더하면서 누적 합을 구한다

for (int k = 1; k < M + 1; k++)
	{
		scanf("%d %d", &i, &j);
		printf("%d\n", sum[j] - sum[i - 1]);
	}

그리고 이제 i번째 수부터 j번째 수까지의 구간 합을 구해야한다

즉 num[ i ]부터 num[ j ]까지의 합을 구해야한다

이미 누적 합을 구해놓았기 때문에

sum[ j ]                  = num[1] + num[2] +                      ...                   + num[ j-1 ] + num[ j ]

sum[ i-1 ]               = num[1] + num[2] + ... + num[ i-2 ] + num[ i-1 ]

sum[ j ] - sum[ i-1 ] = num[ i ] + num[ i+1 ] + ... + num[ j-1 ] + num[ j ]

이렇게 누적 합을 쌓아놓은 sum배열의 뺄셈을 통해서 원하는 구간의 합을 구할 수 있다

 

 

위의 내용을 통해서, 누적 합 관련 문제의 풀이과정은 크게 2가지 단계를 나눌 수 있다

1) 합을 누적하는 단계

여기서는 위의 예시처럼 입력된 값을 그대로 새로운 배열에 더할 수도 있겠지만

2559번 문제처럼 새로운 배열이 아닌 새로운 변수에 더할 수도 있고,

11660번 문제처럼 입력받은 2차원 배열에다가 이전 값들을 더하며, 기존 2차원 배열을 누적 합 배열로 바꿀 수도 있다

2) 누적된 합을 토대로 구하고자하는 구간의 합을 구하는 단계

여기서는 앞의 과정을 통해서 만들어놓은 누적 합으로부터 원하는 값을 뽑아내야한다

그렇기에 지금의 단계를 고려해서, 가장 처음에 누적 합을 받은 배열을 몇차원으로 만들것인지,

만든다면 각각의 행/열이 의미하는 바가 무엇인지를 길게 생각해서 풀이를 진행해야한다

16139번 문제처럼 2차원 배열을 알파벳 / 종료점으로 잡을 수도 있다