백준 2018[수들의 합 5]

1. 문제분석 및 접근법

• n의 최댓값이 10^7이기 때문에 O(nlogn)으로도 시간초과가 남
• O(n)의 알고리즘을 채택해야함
• 투 포인터로 접근

1. 1~입력받은 값까지의 리스트 생성
2. 카운트, start, end 변수 생성
3. start~end까지 더 하면서 투포인터 이동원칙으로 이동
4. n과 일치하면 cnt+1, 아니면 start나 end를 이동시킴
5. cnt 출력

2. 슈도코드

실패

n 입력받기
two_pointer 빈 배열
for 1~n+1:
	two_pointer 배열에 추가(append)
cnt, sum, start_index, end_index 변수 생성

while True:
	if start_index가 n보다 커지면:
    	break
	sum = two_pointer[start_index] + two_pointer[end_index]
    if sum이 n보다 작으면:
    	sum = sum + two_pointer[end_index]
        end_index += 1
    elif sum이 n보다 크면:
    	sum = sum - two_pointer[start_index]
    	start_index += 1
    else:
    	start_index += 1
        sum = 0
        cnt += 1

cnt출력

• start_index, end_index가 원소의 값과 동일하기 때문에 따로 배열을 만들 필요 없음
• start_index와 end_index자체를 +=, -=로 연산하면 됨
• while문 종료조건 바로 써주기

재구현

n 입력받기
cnt, sum, start_index, end_index 변수 생성

while end_index가 n과 다르면:
	
    if sum이 n보다 크면:
    	sum -= start_index
        start_index += 1
    elif sum이 n보다 작으면:
        end_index += 1
        sum += end_index
    else:
    	cnt += 1
        end_index += 1
        sum += end_index
        
cnt 출력

3. 코드 구현

import sys
input = sys.stdin.readline

n = int(input())

cnt = 1
sum = 1
start_index = 1
end_index = 1

while end_index != n:
    if sum < n:
        end_index += 1
        sum += end_index
    elif sum > n:
        sum -= start_index
        start_index += 1
    else:
        cnt += 1
        end_index += 1
        sum += end_index

print(cnt)