[백준] 2018번 : 수들의 합 5 C++ 문제풀이 솔루션

문제

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

예제 입력 1 

15

예제 출력 1 

4

 

 

첫 시도때 합 배열을 만들어서 부분합으로 접근했다. 메모리 초과 오류가 발생했다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;

int main() {
  fast_io
  int n;
  cin >> n;
  vector<int> sum;
  sum.push_back(0);
  int result = 0;
  for (int i = 1; i < n + 1; i++) {
    sum.push_back(sum[i - 1] + (n - (n - i)));
  }
  int snum = 0;
  int p = 0;
  for (int i = 1; i < n + 1; i++) {
    p = 0;
    while (true) {
      snum = 0;
      snum = (sum[i] - sum[p]);
      p++;
      if (snum == n) {
        result++;
        break;
      }
      if (snum < n) break;
    }
  }
  cout << result;
  return 0;
}

 

두번째 코드는 알고리즘은 동일하고 배열을 순회할때 반복자를 사용해보았다. 물론 메모리 초과

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;

int main() {
  fast_io
  int n;
  cin >> n;
  vector<int> sum;
  sum.push_back(0);
  int result = 0;
  for (int i = 1; i < n + 1; i++) {
    sum.push_back(sum[i - 1] + (n - (n - i)));
  }
  vector<int>::iterator start_idx = sum.begin();
  vector<int>::iterator end_idx = sum.begin() + 1;

  while (true) {
    int nsum = 0;
    nsum = *end_idx - *start_idx;
    if (nsum == n) {
      start_idx = sum.begin();
      result++;
      if (end_idx == sum.end()-1) break;
      else end_idx += 1;
    }
    if (end_idx == start_idx) {
      start_idx = sum. begin();
      if (end_idx == sum.end()-1) break;
      else end_idx += 1;
    }
    start_idx++;
  }
  result++;
  cout << result;
  return 0;
}

 

세번째 코드는 굉장히 단순하다. 

투포인터

합 배열을 선언하여 배열을 이중으로 순회하며 부분합을 구하는게 아닌, 인덱스 2개를 한개씩 움직이면서 부분합을 구했다. right 인덱스를 오른쪽으로 옮기는 것은 다음 자연수를 더하는 것을 의미하며, left 인덱스를 오른쪽으로 옮기는 것은 기존 자연수 중 가장 작은 값을 빼주는 것을 의미한다.

 

이 문제처럼 메모리 제한이 작을때는 배열 선언하는 것이 아닌 투포인터를 사용해야한다.

#include <iostream>
#include <algorithm>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;

int main() {
  fast_io
  int n;
  cin >> n;
  int sum = 0;
  int result = 0;
  int left = 0;
  int right = 0;
  while (true) {
    if (sum < n) {
      right++;
      sum += right;
    }
    if (sum > n) {
      left++;
      sum -= left;
    }
    if (sum == n) {
      result++;
      right++;
      sum += right;
    }
    if (left == n - 1) break;
  }
  cout << result;
  return 0;
}