Python 투포인터 이동 원칙(백준 2018 수들의 합 5)

투 포인터

• 투 포인터(Two Pointer)란?
  ➡️ 2개의 포인터를 사용하여 특정 조건을 만족하는 구간이나 숫자의 쌍을 구하는 알고리즘이다. 주로 정렬된 배열에서 사용된다. 정렬된 배열이란 예를 들어 리스트에 숫자가 1~10까지 있을때, 이 리스트의 형식을 정렬된 배열이라고 한다.

다음과 같은 배열이 있을때 left는 시작을 의미한다(우리는 글을 왼쪽에서 오른쪽으로 읽듯이).
반대로 right는 끝을 의미한다.

이렇게 되면 우리가 선택한 구간은 left~right가 되는것이다

이 리스트에서는 시작값이 1이 되고 끝나는 값이 3이 되므로 구간은 1~3이 된다. 이때 sum함수를 사용하면 1+2+3이 된다 

 

만약 문제에서 목표 값 N이 주어진다면, sum과 N을 비교하여 움직이면 된다.

문제

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1

15

입력으로 15가 주어졌다는것은 1~15까지의 숫자들 중에서 숫자들의 합을 통해 15를 몇개 만들수 있는지 구하는 문제이다
15는 숫자 0+15, 7+8, 4+5+6, 1+2+3+4+5 총 4개로 나타낼 수 있다

예제 출력 1 

4

그러므로 답이 4개가 된다

 

n = int(input())
end = 0
current_sum = 0
count = 0

for start in range(n):
    while current_sum < n and end < n:
        end += 1
        current_sum += end
    if current_sum == n:
        count += 1
    current_sum -= start + 1

print(count)

이 코드는 정답 코드이다. 일단 처음에 시작값과 끝나는 값을 알 수 없기 때문에 변수로 시작값과 끝나는 값을 0으로 정해준다.

그리고 for문 안에다가 현재값과 입력받은 n값을 비교하면서 현재값이 n보다 작고 end도 n보다 작으면 end에 1을 더해간다. 또한 현재값에 end를 더해간다.while 문이 끝나면 if문을 사용해서 현재값이 입력받은 n과 같은지 비교해준다. 비교했을때 같지 않다면 while문으로 더해나간 count를 출력해주고, 현재값과 n이 같다면 count에 1씩 더해간다. 현재값과 n이 같은것까지 비교했으니 마지막으로 n많큼 현재값에 시작과 1을 더한건 차례대로 빼준다. 그 후 count를 출력하면 정답이 된다.