출처: https://www.acmicpc.net/problem/2003
문제 풀이에 앞서
위 문제는 시간 제한이 0.5초이고 N은 10000까지 제한이 되어있는 상태입니다.
그리고 문제에서 요구하는 바를 보면, sequence의 subsequence의 합이 M이 되는 경우의 수를 계산하는 것을 요구하고 있습니다.
이런 문제에서는 구간합 알고리즘이 제일 유용하고, 메모리를 절약함과 동시에 시간복잡도를 덜어낼 수 있는데요, 일단 구간합 알고리즘부터 알아보고 가겠습니다.
수학 얘기좀 할게요. 다들 고등학교 때 배운 partial sum에 관한 내용입니다.
partial sum Sn을 다음과 같이 정의를 하고 시작하겠습니다.
sequence {ai}에 관해서 k부터 n까지의 합을 구해보려고 합니다. 구간합 알고리즘 없이 계산을 하려면 다음과 같이 계산을 해야할겁니다.
sum = 0
for i in range(k, n + 1):
sum += sequence[i]
print(sum)그러나 위의 방법대로 하면 문제가 발생할 수 있습니다.
- 구간합을 매번 계산을 해야하기 때문에 코드의 시간복잡도가 증가할 우려가 있다.
그러므로 저는 아래의 방법으로 계산을 할 예정입니다.
- 수열의 누적 합을 미리 계산을 해둡니다. 그리고 구간합이 필요할 때마다 단순 사칙연산을 통해서 구할 생각입니다.
위의 방법대로 계산을 하기 위해서는 아래의 공식을 알고 계셔야하는데요, 공식은 아래와 같습니다.
저는 위의 공식을 이용해서 문제를 풀 예정입니다. 코드를 보실까요?
코드 먼저 봅시다. 그리고 분석해보죠.
import sys
# 2003 수들의 합
input = sys.stdin.readline
N, M = map(int, input().split())
sum = 0
number_list = [0] # 입력받는 수들의 누적 합을 저장하는 배열, 첫번째 인덱스에는 0을 미리 넣어둔다
for number in map(int, input().split()):
sum += number
number_list.append(sum)
start, end = 1, N
first = 1 # 현재 읽어내는 첫번째 수열의 인덱스
count = 0
while start <= end:
# 현재 읽어내는 수열의 합이 M 미만인 경우 -> start에 변화를 주지 않고 넘기면 수열에 포함되는 효과를 가짐
if number_list[start] - number_list[first - 1] < M:
start += 1
# 현재 읽어내는 수열의 합이 M인 경우 -> count를 증가시키고 맨 앞의 숫자를 pop, 그리고 다음 숫자를 읽을 준비
elif number_list[start] - number_list[first - 1] == M:
count += 1
first += 1
start += 1
# 현재 읽어내는 수열의 합이 M보다 큰 경우 -> count를 증가시키지 않는다
else:
first += 1
print(count)일단 number_list에 0을 미리 넣어둔 리스트를 초기화시킵니다. 0을 미리 넣어둔 리스트로 초기화시키는 이유는 0을 미리 넣어둬서 인덱스1부터 합을 저장하기 위해서 입니다.
그리고 number_list에는 처음의 숫자부터 합을 누적시켜서 저장합니다. 예시를 들어드리죠.
🌈 수열 예시
1 2 3 4 5 6 7 8 9 10🌈 number_list에 저장되는 값
0 1 3 6 10 15 21 28 36 45 55그리고 while문을 통해서 subsequence의 합을 계산할겁니다. while문 내부에서는 가능한 경우가 세가지가 될 겁니다.
- subsequence의 합이 M 미만인 경우 -> 다음 숫자를 포함시켜서 다음 판단을 해봐야한다
- subsequence의 합이 M인 경우 -> count를 1 증가시키고, 맨 앞의 숫자를 누락시키고 다음 숫자를 읽어내야한다.
<=> first를 1 증가시키고, start를 1 증가시키고, count도 1 증가시킨다. - subsequence의 합이 M 초과인 경우 -> 맨 앞의 숫자를 누락시킨다. (i.e. first를 1 증가시킨다)
위의 방법으로 매번 구간합을 계산해준 뒤에 count를 출력하면 문제가 해결됩니다.
