코테 대비 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)

투포인터로 주기위한 시간 제한임을 확인하자 

투포인터를 통해 시간중복을 줄이기!!