📗문제 설명

문제 바로가기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	128 MB	44623	21416	14473	48.300%

❓ 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을 넘지 않는 자연수이다.
• 출력
  • 첫째 줄에 경우의 수를 출력한다.
• 예제

  # 입력
  4 2
  1 1 1 1
  # 출력
  3
  

💡문제 풀이 IDEA

1. 첫번째 부터 M값이 넘을때까지 숫자를 더해준다. M이 같아지면 횟수를 +1하고 다음값으로 넘겨준다.
   1. 시간초과 오류가 났다.
2. 투포인터 개념 사용
   1. 리스트를 더할 시작인덱스와 끝 인덱스를 지정해주고 시작 인덱스~ 끝 인덱스의 합을 M값과 비교해나가면서 시작 끝을 움직여준다.

• 만약 더한 값이 더 작다면 end를 1 추가해서 값을 더 더해준다.
• 더한 값이 더 크다면 start를 1 추가해서 값을 더 줄여준다.
  • 만약 값이 같다면 count를 1 추가하고 end를 1 추가해서 앞으로 나아간다.

👨🏻‍💻문제 풀이 CODE

1차 시간초과

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
arr=list(map(int,input().split()))

count=0
for i in range(len(arr)):
    number=0
    if arr[i]>M:
        continue
    elif arr[i]==M:
        count+=1
        continue
    else:
        while number<M and i<N:
            number+=arr[i]
            i+=1
            if number==M:
                count+=1

print(count)

2차 성공

import sys
input=sys.stdin.readline
def main():
    N,M=map(int,input().split())
    arr=list(map(int,input().split()))
    answer=two_pointer(arr,N,M)
    print(answer)

def two_pointer(arr,N,M):
    count=0
    start=0
    end=1
    while start<=end and end<N+1:
        if sum(arr[start:end])==M:
            count+=1
            end+=1
        elif sum(arr[start:end])<M:
            end+=1
        else:
            start+=1

    return (count)

if __name__=="__main__":
    main()