[탐색 & 시물레이션] - 수들의 합

수들의 합

 

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을 넘지 않는 자연수이다.

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

 

▣ 입력예제 1

8 3

1 2 1 3 1 1 1 2

▣ 출력예제 1

5

 

 

나의 코드

n,m=map(int,input().split())
arr=list(map(int,input().split()))

p1=0
p2=1
cnt=0

while p1<n and p2 <n+1 :
    if m>sum(arr[p1:p2]):
        p2+=1
    elif m<sum(arr[p1:p2]):
        p1+=1
    elif m==sum(arr[p1:p2]):
        if p2==n:
            cnt+=1
            p1+=1
        else:
            cnt+=1
            p2+=1
print(cnt)

투 포인터를 사용해서 구현하였다.

뭔가 더 깔끔하게 코드를 짤 수 있을 것같은데..흠..  

 

 

import sys
sys.stdin = open("input.txt", 'r')
n, m=map(int, input().split())
a=list(map(int, input().split()))
lt=0
rt=1
tot=a[0]
cnt=0
while True:
    if tot<m:
        if rt<n:
            tot+=a[rt]
            rt+=1
        else:
            break
    elif tot==m:
        cnt+=1
        tot-=a[lt]
        lt+=1
    else:
        tot-=a[lt]
        lt+=1
print(cnt)

정답 코드도 보니 코드가 깔끔하지가 않다.

나와 비슷하게 투포인터를 썻지만 슬라이싱 연산 대신 리스트로 하나씩 접근하여 더하고 빼고를 반복하며 카운팅하고  break를 걸어주는 로직이 다르다.

코드는 다르더라도 투포인터와 마지막 종료 조건을 고려해야했다는 점만 기억하면 되겠다~