숫자를 연속된 덧셈으로 표현하는 알고리즘

문제

수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은

(1+2+3+4+5)
(4+5+6)
(7+8)
(15)

로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다.

풀이

#include <iostream>
using namespace std;
int expressions(int testCase)
{
  int answer = 0;

  int num = 1, temp = 0;
  for (int i = 1; i <= testCase / 2; i++, temp = 0, num = i)
  {
    while (temp <= testCase)
    {
      temp += num++;
      if (temp == testCase)
        answer++;
    }
  }

  return ++answer;
}

int main()
{
  int testNo     = 15;
  int testAnswer = expressions(testNo);

  // 아래는 테스트로 출력해 보기 위한 코드입니다.
  cout << testAnswer;
}

원래 알고리즘 문제를 풀면서 기본으로 제공되는 코드는 웬만해선 안고치는데

answer 앞에 ++만 붙였다..(괜히 코드가 한 줄이라도 길어지는 것보단 …)

굳이 testCase(15)까지 다 반복하지 않아도 절반 값, 예를 들어 15의 절반은 7(나머지 무시)이기 때문에

7과 그 다음 수인 8까지만 계산하면 된다.

절반 이상의 수, 예를 들어10이면 10과 연속된 자연수를 더해서 15를 만들 수 있는 방법은 존재하지 않기 때문이다.

그 다음은 그냥 시작하는 수(예제에서는 1, 4, 7)부터 1씩 더해가며 누적하여 원래 값 15가 나오면 종료하는 것이다.

마지막으로 ++를 해준 이유는 위 코드로 자기 자신(15)은 계산되지 않기 때문..(절반까지 했으니까요..)

출처

알고리즘 연습 Level 4 | 프로그래머스