문제
입력으로 양의 정수 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
코드
최종 풀이
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, i, tmp, pos, pt1 = 1, pt2 = 2, cnt = 0;
scanf("%d", &n);
while(pt2 <= n) {
vector<int> a(pt2 + 1);
tmp = n;
for(i = pt1; i <= pt2; i++) {
tmp -= i;
}
if(tmp < 0) {
break;
} else if(tmp % pt2 == 0) {
pos = tmp / pt2;
printf("%d ", pos + 1);
for(i = 2; i <= pt2; i++) {
printf("+ %d ", pos + i);
}
printf("= %d\n", n);
pt2++;
cnt++;
} else {
pt2++;
}
}
printf("%d", cnt);
return 0;
}
설명
각 연속된 자연수의 첫 번째와 마지막 point를 각각 pt1, pt2으로 선언하고 pt1은 1로 pt2는 2로 초기화한다.
사용자로부터 양의 정수 N을 입력받고 pt2가 n보다 작을 때까지 반복하는 while문을 작성한다.
이후 pt1~pt2까지 값을 할당받을 vector a를 만든다.(pt2 + 1) 또한 n의 값을 pt1~pt2까지 빼야하므로 tmp에 n을 할당하면서 tp1~tp2까지 반복하는 for문을 작성하여 tmp를 빼나간다.
뺀 tmp값을 pt2로 나누었을 때 나머지가 0인 경우 pt2만큼의 연속된 자연수가 있다는 의미이므로 tmp를 pt2로 나눈 값을 pos변수에 할당한다.
+ 연산자 출력을 고려해야하므로 첫 번째 자연수를 먼저 출력해야한다. 따라서 pos + 1값을 먼저 출력하고 두 번째 자연수에서 마지막 자연수까지 반복하는 for문을 작성하여 + 연산자와 pos를 1씩 더한 값을 함께 출력한다.
해당 for문이 끝나면 최종 합을 출력해야하므로 =와 함께 n(=최종 합)을 출력한다.이후 다음 가짓수를 찾기 위해 pt2를 1증가하고 cnt또한 1증가한다.만약 tmp값을 pt2로 나누었을 때 나머지가 0이 아닌 경우 n에 해당하는 연속된 자연수가 포함되어있지 않는다는 것을 의미하므로 다음 가짓수를 찾기 위해 pt2만 1증가한다.마지막으로 tmp값이 0보다 작을 경우 음수의 경우까지 찾게 되므로 break를 걸어 while문을 빠져나온다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
