[PS - Do It!] 3-3. 자료구조 : 투 포인터(1)

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

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

예제 입력 1 

15

예제 출력 1 

4

 

• 선형 시간 O(N)으로 처리해야 하므로 투 포인터 알고리즘이 적합
• for loop 로 start를 하나씩 증가키면서 반복
• while loop를 사용해서 각 start당 최대한 end를 오른쪽으로 이동
• 이동시키다가 중간에 sums == n이면 cnt+=1

import sys
input = sys.stdin.readline

# 자연수 n 입력받기 : 연속된 자연수의 합 = n이 되도록 설정
n = int(input())

# 투 포인터 알고리즘을 이용 : O(N)
array = list(range(1,n+1))
end = cnt = 0
sums = array[0]

# start, end는 index로 해석
# start를 차례대로 증가시키며 반복

for start in range(n) : 
    # end를 가능한 만큼 이동시키기
    while sums < n and end < n :
        end +=1
        sums +=array[end]
        
    if sums == n :
        cnt+=1
    
    sums -= array[start]
    
print(cnt)

• 다만 위의 풀이는 메모리초과 가 뜬다!
• 만들어준 리스트의 크기가 n이기 때문에 메모리초과인데, 위의 풀이처럼 리스트를 만들어서 index로 접근하는 풀이법은 문제가 1,2,3,...처럼 순서대로 배열이 있지 않는 경우의 일반적인 풀이법이다
• 이 문제의 경우 숫자가 순서대로 배열되어 있으니 굳이 리스트의 원소로 접근하지 말고 숫자 그 자체로 접근하면 된다

import sys
input = sys.stdin.readline

# 자연수 n 입력받기 : 연속된 자연수의 합 = n이 되도록 설정
n = int(input())

# 투 포인터 알고리즘을 이용 : O(N)
cnt = 0
end = 1
sums = 1

# start, end는 index로 해석
# start를 차례대로 증가시키며 반복

for start in range(1,n+1) : 
    # end를 가능한 만큼 이동시키기
    while sums < n and end < n+1 :
        end +=1
        sums +=end
        
    if sums == n :
        cnt+=1
    
    sums -=start
    
print(cnt)