[Python-CodingTest] 3-5. 수들의 합

수들의 합

문제 정리

입력

8 3
1 2 1 3 1 1 1 2

처리 과정

1. 두개의 포인터 변수(p1,p2) 초기화 p1=0 p2=1
2. tot: lst[p1]부터 lst[p2] “이전”까지의 합
3. tot<m tot==m tot>m으로 경우의 수 나눠서 작성
4. tot<m이면 p2<n인 경우에만 tot에 값을 더하고 p2는 다음으로 이동
5. tot==m이면 카운트 하고 tot에서 lst[p1] 값을 뺀 뒤에 p1은 다음으로 이동
6. tot>m이면 카운트는 안하고 5번과 마찬가지로 작성

출력

5

풀이

import sys
sys.stdin = open("./input/in5.txt", "rt")

n,m = map(int, input().split())
lst = list(map(int, input().split()))

# 포인터 변수 초기화
p1=0
p2=1 

tot=lst[0] # lst[p1]부터 lst[p2] "이전"까지의 합 (초기화는 lst[0]으로)
cnt=0 # 경우의 수

while True:
    if tot<m:
        if p2<n:
            tot+=lst[p2] # 이후에 p2+=1 하니까 tot에는 lst[p2]를 더하는게 맞음
            p2+=1
        else:
            break
    elif tot==m:
        cnt+=1
        tot-=lst[p1]
        p1+=1
    else:
        tot-=lst[p1]
        p1+=1
print(cnt)

정리

• 두 개의 포인터 변수를 이용해 풀기
• tot<m인 경우에서 if p2<n에 등호가 들어가지 않는 이유?

  p2<=n이 아닌 이유는 tot<m인 경우에는 p2가 n-1일 때까지만 해당 if문 통과할 수 있고,
  p2+=1을 통해 n이 되면 tot==m이거나 tot>m인 경우에만 진행 가능하며 tot<m일 경우에는 break 해야하기 때문

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기