(2024 대회 준비) 수들의 합 5 - 2018번

문제

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

예제 입력

15

예제 출력

4

코드

#include <iostream>

using namespace std;

int n, l = 1, r = 1, sum, ans;

int main() 
{
    cin >> n;

    while (l <= r && r <= n) 
    {
        if (sum < n) sum += r++;

        else 
        {
            if (sum == n) ans++;
            sum -= l++;
        }
    }

    cout << ans + 1;
}

설명

너무 어렵게 생각하지 말자.

 

처음에는 추가로 더해주는 숫자들을 몽땅 더해서 원래 수에다가 뺀다음 나타내는 갯수로 나누어서 1보다 아래로.. 어쩌구 저쩌구..

=> 표현하기도 힘들고 답도 틀렸다.

 

먼저 무슨 알고리즘인지 파악

연속하는 수들의 합이므로 이것과 관련된 알고리즘을 생각할 것!

 

맞는 알고리즘은 코드로 보고 이해해볼 것

하나씩 다 더해서 넘거나 같은 경우에 처음 else문으로 들어간다.

같으면 답을 하나 추가해주고 아닌 경우(넘는 경우)에는 가장 작은 l을 빼주고 l을 증가시켜준다.