(Python/🥈4)백준 알고리즘 2003번 : 수들의 합 2

 

문제 바로가기 

수들의 합2

문제: 

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

출력:

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

 

풀이:

 

이 문제는 투포인터로 풀어야 한다.

하지만 dp로 풀어보고 싶어 2차원 dp로 했는데 시간초과 나버렸다.

 

 

n, m = map(int, sys.stdin.readline().split(" "))
Number = list(map(int, sys.stdin.readline().split(" ")))

dp = [[0] * (n) for _ in range(n)]
for i in range(n):
    dp[i][i] = Number[i]

# 시작 좌표
count = 0
for x in range(n):
    # 도착 좌표
    for y in range(x + 1, n):
        if dp[x][y-1] > m:
            break
        dp[x][y] = dp[x][y - 1] + Number[y]

for i in dp:
    count += i.count(m)
print(count)

 

모든 구간합을 dp에 저장하는 식인데 너무 많을꺼 같아 m이 넘어가면 break 하기로 했지만 메모리 초과가 난다.

 

 

풀이2.

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, sys.stdin.readline().split(" "))
Number = list(map(int, sys.stdin.readline().split(" ")))

left = 0; right = 0

count = 0
while right < n:
    res = sum(Number[left:right+1])
    if res == m:
        count += 1
        right += 1
    elif res > m:
        left += 1
    else:
        right += 1
print(count)

 

그냥 투포인터로 풀어서 맞췄다.