[Do-it! 코딩 테스트-기초편] 006. 연속된 자연수의 합 구하기

문제

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

2018번: 수들의 합 5

---

접근

데이터 크기: 10,000,000

시간 제한: 2초

 

반복문을 사용해서 N까지의 숫자중 연속된 합을 모두 구하려면 시간이 초과된다.

이중 반복문을 사용하면 최소 O(N^2)의 시간복잡도를 가진다.

 

시간을 줄이기 위해서 투 포인터 방법을 사용해야한다.

시작 인덱스와 끝 인덱스를 지정한 후 각각을 조건에 따라 이동시켜 원하는 값인지 확인하는 방법으로 접근한다.

---

코드

import sys

# 1
def cal(n, m):
    return (n + m) * (m - n + 1) // 2

N = int(sys.stdin.readline())
cnt = 1 # 2

i = 1
j = 1

# 3
while j <= N//2 + 1:
    if i == N and j == N:
        break
        
    # i와 j의 변화를 출력    
    # print(f'i: {i}, j: {j}')
    # 4
    if cal(i, j) == N:
        cnt += 1
        
        # 조건이 만족할 때 cnt를 증가
        # print(f'cnt: {cnt}')
    # 5
    if cal(i, j) <= N:
        j += 1
    elif cal(i, j) > N:
        i += 1

print(cnt)

---

설명

# 1

N부터 M까지의 합을 구하는 함수

i와 j의 값에 따라 그 사이의 연속된 값의 합을 구하는 함수를 따로 지정해주었다.

 

# 2

자기 자신을 포함해야 하기 때문에 cnt를 0이 아닌 1로 초기화한다.

 

# 3

연속된 숫자의 합이 N이 될 수 있는 최소 개수는 2개이다.

15를 예로 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 중 7 + 8 이 조건에 만족하는 가장 큰 값들의 조합이다.

(N의 중간값 + 1) 보다 큰 숫자는 볼 필요가 없다는 뜻이다.

따라서 while의 조건을 위와 같이 주었다.

 

첫번째 조건문은 N=1과 N=2에서 발생하는 예외를 방지하기 위해서이다.

1과 2는 중간값보다 큰 값을 제외하면 연산이 성립되지 않는다.

 

# 4

cal의 연산 결과가 N과 같으면 cnt를 증가시킨다.

 

# 5

시작 인덱스가 i이고 끝 인덱스가 j이다.

끝 인덱스는 시작 인덱스보다 작을 수 없기 때문에 끝 인덱스 j를 먼저 이동시킨다.

두 포인터가 시작하는 지점은 1이고 1과 1의 합은 N보다 항상 작기 때문에 j가 먼저 증가한다.

j가 증가하면 i=1 j=2 에 위치하고 cal 연산을 통해 두 포인터 사이 값들의 합을 구한다.

만약 그 값이 N보다 작으면 j를 증가시키고 N보다 크면 i를 증가시킨다.

( j가 증가하면 합이 커지고 i가 증가하면 합이 작아진다. )

---

피드백

책의 코드와 전반적인 개념은 같다. 하지만 해답은 cal함수 대신 sum 변수를 지정하여 각각의 포인터가 이동할 때 값을 더하거나 빼는 방식을 사용하였다.

sum이 N보다 작으면 끝 인덱스가 증가하고 sum에 끝 인덱스 값을 더한다.

sum이 N보다 크면 시작 인덱스가 증가하고 sum에 시작 인덱스 값을 뺀다.

이 과정에서 sum이 N과 같을 경우 count를 증가하여 정답을 구한다.

 

시간 복잡도를 고려했을 때 반복마다 해야하는 연산이 비교적 적다는 생각이 들었다.

그래서..

해답의 아이디어로 코드를 수정해보았다

절반만 확인

import sys

N = int(sys.stdin.readline())
cnt = 1
i = 1
j = 1
sum = 1

while j <= N//2 + 1:
    if i == N and j == N:
        break
    if sum == N:
        cnt += 1
    if sum <= N:
        j += 1
        sum += j
    elif sum > N:
        sum -= i
        i += 1

print(cnt)

전체 확인

import sys

N = int(sys.stdin.readline())
cnt = 1

i = 1
j = 1
sum = 1

while j != N:
    if sum == N:
        cnt += 1
    if sum <= N:
        j += 1
        sum += j
    elif sum > N:
        sum -= i
        i += 1
        
print(cnt)

당연하게 합을 계산하는 함수를 사용하지 않고 매 반복마다 하나의 연산만 하는 것이 빠르다.

또한 필요한 부분만 연산하는 절반만 확인 코드가 훨씬 빠르다는 결과를 보았다.

 

시간 제한 통과도 중요하지만 필요한 경우 연산 방법이나 알고리즘을 더 효율적으로 구현할 수 있어야 한다.

---

알고리즘

투 포인터