[백준] 2018(수들의 합5)

투포인터

2개의 포인터로 알고리즘의 시간 복잡도를 최적화할 수 있음 

2018

2018번: 수들의 합 5

🐬접근

N의 최댓값이 10,000,000 이므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한시간  2초를 초과함. 따라서 O(n)의 시간 복잡도 알고리즘을 써야함. 

연속된 자연수이므로 투포인터를 활용해 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 수 있음

시작 인덱스(s)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수에서 왼쪽 값을 삭제

종료 인덱스(e)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수 범위 확장

투포인터 이동 원칙
- sum > N : sum -= s ; s += 1;
- sum < N : e += 1; sum += e ;
- sum == N : e += 1, sum += e , cnt += 1;

풀이

import sys
input = sys.stdin.readline

N = int(input())

s,e = 1, 1 # 시작 인덱스, 종료 인덱스 
cnt = 1 #정수 자기 자신포함시킨 상태로 초기화
sum = 1 #1부터 합 시작 

while e != N : # 종료 인덱스가 N 자기 자신이 되기 전까지 수행
    if sum == N : 
        # 합 성립 
        print(f'{N}달성 : {list(range(s,e+1))}')
        cnt += 1
        e += 1
        sum += e
    elif sum > N :
         # N 초과할 경우 시작인덱스를 빼줌
        print(f'{N}초과 : {list(range(s,e+1))}')
        sum -= s 
        s+=1
    else:
    	# 종료 인덱스를 늘려가며 sum 누적
        print(f'{N}미만 : {list(range(s,e+1))}')
        e += 1
        sum += e
print(cnt)

## 출력예시

15

15미만 : [1]
15미만 : [1, 2]
15미만 : [1, 2, 3]
15미만 : [1, 2, 3, 4]
15달성 : [1, 2, 3, 4, 5]
15초과 : [1, 2, 3, 4, 5, 6]
15초과 : [2, 3, 4, 5, 6]
15초과 : [3, 4, 5, 6]
15달성 : [4, 5, 6]
15초과 : [4, 5, 6, 7]
15초과 : [5, 6, 7]
15미만 : [6, 7]
15초과 : [6, 7, 8]
15달성 : [7, 8]
15초과 : [7, 8, 9]
15초과 : [8, 9]
15미만 : [9]
15초과 : [9, 10]
15미만 : [10]
15초과 : [10, 11]
15미만 : [11]
15초과 : [11, 12]
15미만 : [12]
15초과 : [12, 13]
15미만 : [13]
15초과 : [13, 14]
15미만 : [14]