[백준] 수들의 합 2 2003번 (python)

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

2003번: 수들의 합 2

풀이 방법

투 포인터 문제를 연습할 겸 문제를 풀어 보았다. 이중 for문으로 풀면 시간초과가 난다.

투 포인터란 배열을 순회하는 하나의 방법으로 포인터를 2개를 사용해서 순회하는 방법이다.

왼쪽 포인터와 오른쪽 포인터를 두고 풀어보자

왼쪽 포인터부터 오른쪽 포인터까지 합을 리턴하는 함수를 작성한다. 이때 배열의 합에 따라 케이스를 분리하자

• 배열의 합이 M보다 크면 배열의 합을 줄여야 하므로 왼쪽 포인터를 +1 이동한다 
  • 왼쪽 포인터를 +1 하면 더해야하는 배열의 원소 수가 줄어든다. -> 배열의 합 감소
• 배열의 합이 M보다 작으면 배열의 합을 늘려야 하므로 오른쪽 포인터를 +1 시켜준다 
  • 오른쪽 포인터를 +1 하면 더해야하는 배열의 수가 커진다. -> 배열의 합 증가
• M과 배열의 합이 같게 된다면 count를 +1 하고 오른쪽, 왼쪽 포인터를 한 칸 이동시킨다.
  
  • M과 같으면 오른쪽이나 왼쪽 둘 중 하나만 옮겨도 수가 작아지거나 커지므로 둘 다 이동시킨다.

 

while문 탈출 조건에 대해 알아보자

오른쪽 포인터가 배열의 크기를 벗어나게 된다면 종료하면 된다. 케이스를 나누어 생각해 보자

• 만약 오른 쪽 포인터가 마지막 원소에 위치하게 됐을 때 케이스
  • M과 배열의 합이 같음 -> 오른 쪽 포인터 +1 -> 배열의 크기 벗어남
    • 왼쪽 포인터를 +1 이동을 아무리 시켜도 정답이 나올 수 없다.
  • 배열의 합이 M보다 작다 -> 오른 쪽 포인터 +1 -> 배열의 크기 벗어남
    • 왼쪽을 +1 하면 배열의 합이 계속 작아지므로 정답이 나올 수 없다.
  • 배열의 합이 M보다 클 때
    • 왼 쪽 포인터를 +1 하다가 같이 지면 오른쪽 포인터가 배열 사이즈 넘어가므로 종료된다.

위 세 가지 경우를 보면 탈출 조건이 오른쪽 포인터가 배열의 크기를 벗어나게 된다면 종료하면 된다는 걸 알 수 있다.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
st, ed = 0, 0 ## st 왼쪽 포인터 ed 오른쪽 포인터

def arr_sum(st, ed):
    ret = 0
    for i in range(st, ed+1):
        ret += arr[i]
    return ret
def twoPointer():
    global st, ed
    cnt = 0
    while ed < N:        
        next = arr_sum(st, ed) 
        if next == M:
           cnt += 1           
           ed += 1
           st += 1
        elif next < M:
            ed += 1
        else:
            st += 1
    return cnt
print(twoPointer())