[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-5 "수들의 합"

수들의 합

[시간복잡도]

O(N) 

: While문을 통해서 반복을 진행하고, 

[공간복잡도]

O(N)

 

Problem

수들의 합 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다.

이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

▣ 입력설명

 

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

▣ 출력설명

 

첫째 줄에 경우의 수를 출력한다.

 

▣ 입력예제

 

8 3

1 2 1 3 1 1 1 2

 

▣ 출력예제

 

5

 

💯 Solution ①

: 문제를 풀지 못해서 튜터님의 코드 참고

 

import sys
sys.stdin=open("input.txt","rt")
 
# n은 수열의 갯수 / m은 수열의 총합이 되어야할 수
n, m = map(int,input().split())
n_list=list(map(int,input().split()))
 
# 합을 통해서 m을 만들었을 경우, cnt+=1
cnt=0
 
# point:가르키는 부분
point1=0
point2=1
 
# 더해지는 값 (m과 비교하는 값)
res=n_list[0]
 
while True:
    if res<m:
        if point2<n:
            res+=n_list[point2]
            point2+=1
        else:
            break
    elif res==m:
        cnt+=1
        res-=n_list[point1]
        point1+=1
    else:
        res-=n_list[point1]
        point1+=1
 
print(cnt)

 

💯 Solution ②

 

import sys
sys.stdin=open("input.txt","rt")
n, m=map(int, input().split())
a=list(map(int,input().split()))
# lt,rt 두 개의 포인터를 두고 시작한다. (lt는 처음 / rt는 그 다음)
lt=0
rt=1
# 첫 시작값을 a[0]으로 tot에 담는다.
tot=a[0]
# 합이 m이 되는 경우의 수를 cnt에 담음
cnt=0
 
# True 로 무조건 반복문을 돌게한다.
while True:
    # tot : 수들의 합이 m값보다 작을 때
    if tot<m:
        # n개의 수열보다 rt의 포인터가 작을때
        if rt<n:
            tot+=a[rt]
            rt+=1
        # rt가 n이 된 경우 (더 이상의 자료를 더할 것이 없다.)
        else:
            break
    # m과 연속된 수의 합(tot)값이 같을 때
    elif tot=m:
        cnt+=1
        tot-=a[lt]
        lt+=1
        
    # tot값이 m보다 큰 경우
    else:
        tot-=a[lt]
        lt+=1
 
print(cnt)

- point 로 2개를 배정한다. lt / rt => lt는 제일 처음 값, rt는 그 다음 값으로 배정

- tot에는 연속되는 수들의 합을 담는 변수이다.

- cnt에는 m의 값을 만드는 수들을 찾게되면 +1을 한다.

- 반복문을 돌면서, tot와 m의 값을 비교한다.

- (tot<m) 경우, 수들의 합이 m보다 작기 때문에 추가로 수들을 더해줘야한다.

=> 앞에 있는 포인터 (rt)가 수열의 범위 안에 있다면 tot에 a[rt]에 값을 더하고, rt에 +1을 하면 된다.

하지만, n의 범위를 벗어나서 rt가 있다면 반복문을 멈춰야한다. (그래야 a의 범위를 다 돈 것이기 때문에)

- (tot=m) 일 때는, cnt에 1을 더하고, tot값을 다시 초기화시키기위해서 a[lt]를 뺀다. 그리고 다음 수들을 측정하기 위해서 lt에 1을 더한다.

- (tot>m) 일 때는, tot에서 a[lt]를 빼고 다음 수들의 합으로 이동한다. (lt+=1)

 

해당 코드를 반복해서 break로 반복문을 빠져나간 뒤에 print(cnt)를 하면 m을 구성할 수 있는 수들의 합의 경우를 측정할 수 있다.

 

📚 참고