[ BOJ 2003 ] 수들의 합2(Python)

uoayop·2021년 6월 1일
0

알고리즘 문제

목록 보기
80/103
post-thumbnail

문제

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

투 포인터의 대표 문제 ! ☝🏻


문제 풀이

0. 입력 받기

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))

1. 투 포인터를 움직이면서 값 비교하기

  • 순차적으로 탐색하기 위해 l 포인터는 for문으로 호출한다.
  • hapm보다 작고, r 포인터가 범위 내에 있는 동안에 해당되는 요소들을 hap에 더한다.
  • 만약 hapm과 같다면 answer += 1
  • 한 칸 이동하기 위해 hap에서 l 포인터가 가리키는 숫자를 빼준다.
l, r = 0, 0
answer, hap = 0, 0

# l을 차례대로 증가시키며 반복
for l in range(n):

    # r을 가능한만큼 움직이기
    while hap < m and r < n:
        hap += nums[r]
        r += 1

    # 부분 합이 m일 때 카운트 증가
    if hap == m:
        answer += 1
        
    # m보다 hap이 크거나 같으므로 l 한칸 이동 
    hap -= nums[l]

코드

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))

l, r = 0, 0
answer, hap = 0, 0

for l in range(n):
    while hap < m and r < n:
        hap += nums[r]
        r += 1
    if hap == m:
        answer += 1
    hap -= nums[l]

print(answer)
profile
slow and steady wins the race 🐢

0개의 댓글