코딩테스트/백준

[백준][C++]2018번 수들의 합 5

윤깡패 2023. 6. 15. 16:47

문제

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

 

2018번: 수들의 합 5

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한

www.acmicpc.net

 

 

풀이

투 포인터 알고리즘

 

투 포인터 알고리즘

투 포인터 알고리즘 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정 - 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와 B의 데이터

soobin0821.tistory.com

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

  int N;
  cin >> N;

  vector<bool> result(N + 1, false);

  for(int i = N; i >= 1; i--)
  {
    int sum = 0;	// 현재 연속된 합 값을 저장하는 변수

    for(int j = i; j >= 1; j--)
    {
      sum += j;	// sum값 변경
      if(sum == N)	// 답을 찾았을 때
      {
        result[i] = true;
        break;
      }
      else if(sum > N)	// 현재 합이 답보다 클 때
      {
        break;
      }
    }
  }

  int count = 0;
  for(int i = 1; i <= N; i++)
  {
    if(result[i])
    {
      count++;	// 경우의 수 증가
    }
  }

  cout << count;	// 경우의 수 출력

  return 0;
}

 

 

 

728x90