[백준 2018] 투 포인터 알고리즘 - 파이썬(Python)

수들의 합 5

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

---

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

---

예제 입력

15

예제 출력

4

---

투 포인터 알고리즘

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태입니다.

완전 탐색으로 문제 풀때 시간초과가 나는 경우가 있는데, 투 포인터 알고리즘은 포인터가 한칸 씩 움직이면서 그 변화만 더하거나 빼주면 되므로 시간 복잡도를 줄일 수 있습니다.

 

이번 문제 처럼 연속된 자연수들의 합을 구하는 것을 예시로 보여드리겠습니다. (아래는 배열이 아니라 연속된 수를 나열한 것입니다.)

start_index = 1 , end_index = 5 , SUM = 15

1

2

3

4

5

6

7

8

9

10

 

start_index = 2 , end_index = 5 , SUM = 15 - 1 = 14

이전의  star_index를 sum에서 빼면 바로 다음 2,3,4,5의 합을 구할수 있습니다.

1

2

3

4

5

6

7

8

9

10

 

start_index = 2 , end_index = 6 , SUM = 15 + 6

6으로 올라간  end_index를 sum에서 더하면 바로 다음 2,3,4,5,6의 합을 한번에 구할수 있습니다.

1

2

3

4

5

6

7

8

9

10

위와 같이 투포인터가 이동하면서 변화만 적용해주면 빠르게 다음 수들의 합을 구할 수 있습니다.

---

 

투포인터의 이동 원칙

• sum > N(목표) : 값이 너무 크므로 start를 앞으로 이동시킵니다
  • sum - start;  start++;
• sum < N  : 값이 너무 작으므로 end를 앞으로 이동시킵니다.
  • end++; sum+end ;
• sum == N : 해를 문제에선 카운트하라고 했으니 카운트하고, end를 증가시켜 새로운 해를 찾습니다.
  • end++; sum+end; cnt++;

---

파이썬 코드

#two point
import sys
n = int(input())
start, end, cnt , sum = 1,1,1,1
while end < n:
    if sum<n :
        end+=1
        sum+=end
    elif sum==n :
        cnt+=1
        end+=1
        sum+=end
    else:
        sum-=start
        start+=1
print(cnt)