연속된 자연수의 합 / c / 제한시간 없음

▣ 문제

입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방 법의 가짓수를 출력하는 프로그램을 작성하세요.

만약 N=15이면

7+8=15

4+5+6=15

1+2+3+4+5=15

와 같이 총 3가지의 경우가 존재한다.

 

▣ 입력설명

- 첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어진다.

 

▣ 출력설명

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

 

▣ 입력 예시

15

 

▣ 출력 예시

7 + 8 = 15 4 + 5 + 6 = 15 1 + 2 + 3 + 4 + 5 = 15 3

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, i, j, cnt = 0;
	int sum;
	int temp[500] = { 0 };
	int p1 = 0;
	scanf("%d", &n);
	for (i = n / 2 + 1; i >= 1; i--) {
		sum = 0;
		p1 = 0;
		for (j = i; j >= 1; j--) {
			sum = sum + j;
			temp[p1++] = j;
			if (sum == n) {
				cnt++;
				break;
			}
		}
		if (sum == n) {
			for (j = p1 - 1; j > 0; j--) {
				printf("%d + ", temp[j]);
			}
			printf("%d = %d\n", temp[0], n);
		}
	}



	printf("%d\n", cnt);

	return 0;
}

어떤 정수를 연속된 자연수의 합으로 나타낼때 가장 큰 자연수는 N값의 절반이기 때문에

 

i for문에서 시작을 n/2+1로 잡고

 

j for문에서 i에서 하나씩 작아지는 자연수는 temp라는 배열에 합은 sum에 저장한다

 

만약 sum과 N이 같으면 cnt++ & break 문을 걸고

 

그때까지 저장되어있는 temp 값을 출력한다

 

맨 끝에는 cnt를 출력한다

 

 

<수정된 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, a = 1, cnt = 0;
	int temp;
	int i;

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

	printf("%d\n", cnt);
	return 0;
}

 

 

N이 연속된 자연수의 합으로 표현되는 방법은 최소 2개 이상이어야한다

 

만약 N=15라면

 

연속되는 숫자 2개로 나타낼수 있는지 판단 하기 위해서

 

1, 2를 설정해두고

 

15 - (1 + 2) = 12

       ㄴ연속되는 숫자

12 % 2 = 0

       ㄴ연속되는 숫자의 수

12 / 2 = 6

      ㄴ연속되는 숫자의 수

연속되는 수 : 1 + 6, 2 + 6 = 7 , 8 이 된다. 

 

코드에서는 a가 연속되는 숫자의 수를 나타낸다.

 

while문에서 n=n-a는 N - (연속되는 숫자의 합)를 계속 초기화 시켜준다.

 

.

 

수정한 코드는 확인하고도 한참을 들어다 보았는데

 

내가 자리에서 저렇게 생각해서 풀기에는 벅찬듯함

 

코드 구현에 성공한것에 일단 만족