[백준알고리즘] 2003번: 수들의 합 2 -Python

[백준알고리즘] 2003번: 수들의 합 2 -Python

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

두 가지 방법으로 문제를 해결했다. 쉽게 봤다가 시간제한이 0.5 임을 나중에 보고 Python으로 포기하기도 했었다.. 결국 Python으로도 통과하긴 했다.

1. 연속합을 직접 구해준 방법
2. 더블 포인터를 사용해 값을 찾아간 방법

 

1번 방법

처음에는 1부터 I까지의 합에서 1부터 J까지의 합을 빼서 J부터 K까지의 값을 구했었다.

코드가 막히고 지우고 다시 짜면서 그냥 인덱스 lo부터 hi까지의 연속합을 구하는 코드가 되었다.

 

양수만 계속 더하기 때문에 m보다 합이 커지는 경우는 넘어가도록 해주었다.

 

이 방법으로는 PyPy만 통과할 수 있었다. 반면 2번 방법으로는 Python으로도 통과했다.

import sys

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

cnt = 0
for lo in range(n):
    tmp = 0
    for hi in range(lo, n):
        tmp += arr[hi]
        if tmp == m:
            cnt += 1
            break
        elif tmp > m:
            break

print(cnt)

 

2번 방법

이번에는 low pointer와 high pointer를 두개 두어 합을 연속적으로 구해주었다.

 

더해가는 상황에 맞춰서 low 포인터를 올리거나 high 포인터를 올렸다. 각각의 경우 연속합을 저장하던 tmp에서 arr[low]를 빼건 arr[high]를 더해주었다.

 

이렇게 포인터를 이용한 방식이 위의 코드에서 중복되서 덧셈을 연산하는 경우를 제외시켜주기 때문에 시간제한을 피할 수 있던 것 같다.

import sys

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

cnt = 0
lo, hi = 0, 1
tmp = arr[lo]
while lo < n:
    if tmp == m:
        cnt += 1
        tmp -= arr[lo]
        lo += 1
    
    if hi == n and tmp < m:
        break
    elif tmp < m:
        tmp += arr[hi]
        hi += 1
    elif tmp > m:
        tmp -= arr[lo]
        lo += 1

print(cnt)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다