[Do-it 코딩 테스트] 006. 연속된 자연수의 합 구하기(2018)

문제

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

2018번: 수들의 합 5

---

코드

내가 작성한 코드

num = int(input())
start, end = 1, 1
count = 1
sum = 1

while  end != num:
    if sum == num:
        count += 1
        end += 1
        sum += end
    elif sum > num:
        sum -= start
        start += 1
    else:
        end += 1
        sum += end

print(count)

---

해석

예제 입력	예제 출력
15 #N	4

num = int(input())
start, end = 1, 1
count = 1
sum = 1

 

이 문제는 1 ~ N까지의 수 중에 몇 개의  연속된 합이 N을 나타내는 수를 구하는 문제이다.

우선 N의 수를 입력받기  위해 input()을 사용하여 num에 N을 담아주었고

 

이 문제를 풀기  위해서는 투 포인터를 이용하여 쉽게 풀 수 있는데 투 포인터란

간단하게 설명하자면 두개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 방법이다.

 

그래서 나는 start, end 변수에 값 1을 초기화해주고 연속된 합이 N을 나타낼때마다 count를 + 1씩 올려주기 위해 count라는 변수를 선언해주었다.

여기서 count를 1로 넣어준 이유는 자기자신 즉N도 포함이기때문에 count가 0이 아닌 1부터 시작하였다.

연속된 합의 값을 계산하기 위해 sum이라는 변수를 선언 후 초기값을 1로 설정해두었다.

 

while  end != num:
    if sum == num:
        count += 1
        end += 1
        sum += end
    elif sum > num:
        sum -= start
        start += 1
    else:
        end += 1
        sum += end

몇번을 돌릴지 모르기 때문에 for문 말고 while문을 사용하였고

while문에 조건을 사용해주지 않으면 무한루프에 빠질  수 있어 end != num: end포인터가 N의 값과 같을 때 while문을 탈출하게 해주었다.

 

여기서 end랑 start는 1부터 시작하기때문에 조건문에 end != num 을 사용할 수 있었지만 만약 두 포인터가 양 끝에서 시작한다면 해당 조건은 사용할 수 없다.

 

여기서 while문 안에 조건문을  사용하여 조건에 따라 count와 포인터들을 이동시켜주어야 하는데 여기서 조건은 총 3가지라고 볼 수 있다

 

1. sum(합)의 값과 num(N)이 같을때

두  값이 같을때는 count를 올려주고 end 포인터를 1올려주고 sum에올린 end포인터 값을  더해주면 된다

 

2. sum(합)의 값이 num(N)보다 클때

합이 N보다 클 경우에는 합 - start값을 해주고 start 포인터를 1이동시켜준다.

 

3.  sum(합)의 값이 num(N)보다 작을때

합이 N보다 작을 때 end 포인터를 1 이동시켜주고 1번과 같이 합에서 end포인터 값 만큼 더해주면 된다.

print(count)

그 후 count를 출력해주면 우리가 얻고싶어했던  연속된 합이 N을 나타내는 수를 구할  수 있다.