백준 2018 수들의 합5

문제

---

솔루션

n = int(input())
cnt,sum = 0,0
start, end = 0,0

while end<=n:
    if sum < n:
        end += 1
        sum += end
    elif sum > n:
        sum -= start
        start += 1
    else:
        cnt+=1
        end+=1
        sum+=end
print(cnt)

---

깨달은점

오랜만에 푸려니 기억이 잘 안났다.. 투포인터를 사용해서 풀어야하는 문제였다.

 

cnt,sum = 0,0
start, end = 0,0

• cnt: 연속된 수의 합이 n이 되는 경우의 수를 세는 변수
• sum: 현재 구간에 해당하는 숫자들의 합 저장
• start와 end: 현재 연속된 수열의 시작과 끝 위치를 나타내는 두 포인터

while end<=n:
    if sum < n:
        end += 1
        sum += end
    elif sum > n:
        sum -= start
        start += 1
    else:
        cnt+=1
        end+=1
        sum+=end

• while 반복문
  • end가 n보다 작거나 같을 동안 반복. (n보다 큰 값은 고려할 필요가 없음)
• 현재 합이 n보다 작은 경우
  • 구간의 길이를 늘려야 함 -> end를 오른쪽으로 한 칸 이동, 새로운 end 값을 합에 더함
• 현재 합이 n보다 큰 경우
  • 구간의 합을 줄여야 함 -> 구간의 가장 왼쪽에 있는 값(start)을 뺌, start를 오른쪽으로 한 칸 이동
• 현재 합이 n과 같은 경우
  • 한 가지 경우를 찾은 것 ->  cnt 1 증가
  • 다음 경우의 수도 탐색하기 위해 end를 오른쪽으로 한 칸 이동시키며 해당 값을 sum에 더함