수의 구간 합

인프런 김태원 강사님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

문제

이 문제를 15~20분 정도 고민했는데
접근방식은 맞았던거 같은데 답이 잘 나오지 않아서 강의를 봤다.

#내 풀이
n, m = map(int, input().split())
arr = list(map(int, input().split()))

start = 0
end = 0
sum = 0
cnt = 0
while start < n and end < n:
    if start == end:
        sum = arr[start]
        if sum == m:
            cnt += 1
            end += 1
        elif sum < m:
            end += 1
        else:
            end += 1
    else:
        sum = arr[start] + arr[end]
        if sum == m:
            cnt += 1
            start += 1
        elif sum < m:
            end += 1
        else:
            start += 1

print(cnt)

내가 생각한 방법은 start, end 로 포인터 접근을 해서
투포인터 알고리즘이라 생각하고 목표값과 비교하여 값이 작으면 end를 밀고, 크면 start를 당기고하는것이

나의 의도였는데 코드가 내 생각대로는 움직이지않았다.

---

다음은 풀이 코드이다.

풀이 그림 설명

배열에서 lt와 rt는 인덱스를 가리키는 포인터이고

tot 는 구간의 합인데 처음에는 a[0]의 값을 가진다.

목표값이 m일때

tot가 m보다 작으면, a[rt]값을 tot에 더해주고, rt + 1을 한다.

이때, rt가 n의 길이를 넘어가면 break하여 종료한다.

tot의 값이 m과 같으면, cnt + 1 해주고, tot - a[lt]를 하고, lt + 1을 한다.

tot가 m보다 크면,  tot - a[lt]를 하고, lt + 1을 한다.

 

tot가 m보다 작을때만, a[rt] 값을 더해주는 것이 핵심이다 !!

이 무한루프가 돌면 rt > n 시점에서 반복이 종료된다.

 

#강의 풀이
n, m = map(int, input().split())
a = list(map(int, input().split()))
lt = 0
rt = 1
tot = a[0]
cnt = 0
while True:
    if tot < m:
        if rt < n:
            tot += a[rt]
            rt += 1
        else:
            break
    elif tot == m:
        cnt += 1
        tot -= a[lt]
        lt += 1
    else:
        tot -= a[lt]
        lt += 1

print(cnt)

 

쉬운 문제 같으면서도 잘 안풀렸다.