연속된 자연수의 합 (수리) with c++

처음 이문제의 해결법을 보고나서 조금 충격을 먹어 정리 하고자 합니다.

 

문제

 

입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방
법의 가짓수를 출력하는 프로그램을 작성하세요.만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

▣ 입력설명
첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어진다.

▣ 출력설명
첫줄부터 각각의 경우의 수를 출력한다.
맨 마지막 줄에 총 개수를 출력한다.

▣ 입력예제 1
15

▣ 출력예제 1
7 + 8 = 15
4 + 5 + 6 = 15
1 + 2 + 3 + 4 + 5 = 15
3

 

풀이

 

연속된 자연수가 되는지 확인하기 위해 먼저 1 과 2를 잡습니다. N의 값이 1 과 2를 더한것 보다 작을 경우 연속된 자연수의 합으로 이루어 질수 없는 수이니깐요

 

그리고나서 1 과 2를 N 에서 뺀 값을 더한 숫자의 개수 만큼 나눕니다.

예를 들어 15 - 1 - 2 = 12 -> 12 % 2 = 6

그럼 1 과 2에 각각 6을 더해줘서 7 + 8 의 합으로 이루어 져있다는 것을 알 수 있습니다.

 

그다음도 마찬가지로 15 - 1 - 2 - 3 = 9 -> 9 % 3 = 3

1 + 3, 2 + 3, 3 + 3 으로 4, 5, 6 의 연속된 자연수가 나옵니다.

 

코드로 구현해 보겠습니다.

#include <stdio.h>

int main() {
  int a, b=1, cnt=0, tmp, i;
  scanf("%d", &a);
  tmp = a;
  a--;
  while (a > 0) {
    b++;
    a -= b;
    if (a % b == 0) {
      for (i=1; i<b; i++) {
        printf("%d + ", (a/b)+i);
      }
      printf("%d = %d\n", (a/b)+i, tmp);
      cnt++;
    }
  }
  printf("%d", cnt);
  return 0;
}

 

a 라는 변수에 입력값을 받고 tmp 에 입력값을 저장해 놓습니다. 수식 값에 사용하기 위해서 입니다.

a 에서 1을 뺀 이유는 b의 값을 1로 초기화 하였기 때문입니다.

 

그리고 b 에 1을 더하고 a 에서 b를 뺍니다. 위에서 봤던것 처럼 15 - 1 - 2 가 되었습니다.

요기서 a = 12 b = 2   a % b == 0 이 참인지 확인한뒤 참이면 for 문을 돌면서 수식을 적습니다.

 

코드는 간단하지만 이론적인 부분을 발상하기 되게 어려웠던 문제인거 같습니다.