[백준/CPP/JS] 2737번. 연속 합

[백준] 2737번. 연속 합

1. 문제

대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.

예를 들면 다음과 같다.

6 = 1 + 2 + 3

9 = 5 + 4 = 4 + 3 + 2

하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.

자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오.

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다.

3. 출력

각 테스트 케이스에 대해서 N을 적어도 2개 이상의 연속된 자연수의 합으로 나타내는 경우의 수를 출력한다.

4. 풀이

• n을 입력 받은 후 1을 빼준다.
• i를 2부터 반복한다.
  • n에서 i를 빼준다.
  • n이 i로 나누어 떨어지는지 확인한다.
  • 나누어 떨어지면 count를 증가한다.
• 위의 풀이는 연속된 자연수에 같은 수를 분배해줄 수 있는지 확인하는 방식으로 구현한 풀이다.
  • n에서 1을 빼주는 작업은 숫자를 1을 기록하는 것이다.
  • n에서 i를 빼주는 작업은 i를 기록하는 것이다.
  • i가 2부터 시작하기 때문에 처음에 1과 2가 기록되고 전체 n에서 1+2만큼 빠진다.
  • 기록되고 남은 수를 1과 2에 균등하게 배분할 수 있으면 이미 연속된 자연수에 같은 수가 더해졌기 때문에 해당 수는 연속된 자연수면서 합이 n이 나온다.

5. 처음 코드와 달라진 점

• null

6. 코드 - cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int testcase;
  cin >> testcase;

  for (int tc = 0; tc < testcase; tc++)
  {
    int n;
    cin >> n;

    int count = 0;
    n--;
    for (int i = 2; i <= n; i++)
    {
      n -= i;
      count += n % i == 0 ? 1 : 0;
    }
    cout << count << endl;
  }
}

7. 코드 - js

function solution(nums) {
  let answer = [];

  for (let i = 0; i < nums.length; i++) {
    nums[i]--;
    let count = 0;
    for (let j = 2; j <= nums[i]; j++) {
      nums[i] -= j;
      count += nums[i] % j === 0 ? 1 : 0;
    }
    answer.push(count);
  }
  return answer;
}

console.log(solution([6, 9, 8, 1800, 987654321, 987654323, 987654325]));