코테 대비 python/백준
2003 수들의 합 2
ylab
2023. 3. 20. 20:23
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
#pyp3 버전
#just구현
#N이 10^4까지 이기 때문에 n^2를 해도 괜찮을 것이라고 판단. 0.5초이긴하지만 일단 해보고 안되면 다른방법생각
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = list(map(int,input().split()))
#만족하는 경우 카운트 올리기
cnt=0
for i in range(n):
#만약 i 가 m보다 크다면 무시
if num[i] > m:
continue
if num[i] == m:
cnt+=1
continue
if num[i]< m:
tmp=0
#0을 포함시키면 안돼
for j in range(i,n):
#만약 tmp가 m보다 작다면 계속 하고 같다면 카운트 커지면 그만
tmp +=num[j]
if tmp == m:
cnt+=1
break
if tmp > m:
break
print(cnt)
#python 버전
#투포인터 왼쪽과 오른쪽을 정해서 중복 덧셈 제거
#N이 10^4까지 이기 때문에 n^2를 해도 괜찮을 것이라고 판단. 0.5초이긴하지만 일단 해보고 안되면 다른방법생각
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = list(map(int,input().split()))
#만족하는 경우 카운트 올리기
cnt=0
#왼쪽 가리키기 오른쪽가리키기
left, right = 0, 1
#왼쪽꺼 임시 저장
tmp = num[left]
#왼쪽것이 전체 길이갈때 까지 반복
while left < n:
#만약 임시가 주어진 값과 같다면 더하고 다음 순번으로 넘어감
if tmp == m:
cnt+=1
#tmp 초기화 후 다음 left값 받을준비
tmp-=num[left]
left+=1
#만약 오른쪽이 길이와 같다면 반복 그만함
if right == n and tmp <m:
break
#만약 임시가 정해진 값보다 작다면 임시 값 + 오른쪽 포인터 값 그리고 오른쪽 이동
elif tmp < m:
tmp+=num[right]
right+=1
#tmp 가 값이 커도 다음순번으로 넘어감 그렇지만 카운트는 늘어나지 않음
elif tmp>m:
tmp-=num[left]
left+=1
print(cnt)
투포인터로 주기위한 시간 제한임을 확인하자
투포인터를 통해 시간중복을 줄이기!!