알고리즘/문제풀이
[algorithm 풀이] 5.연속된 자연수의 합
PSYda
2021. 3. 16. 22:33
반응형
0. 문제
입력으로 양의 정수 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
문제 풀이 핵심
- 2개 연속된 수의 경우 숫자에서 1,2를 뺀 값이 2로 나누어지는지 확인한다.
- 3개 연속된 수의 경우 숫자에서 1,2,3을 뺀 값이 3으로 나누어지는지를 확인한다.
- 반복한다.
1. 풀이1 : 오른쪽으로 +1 왼쪽으로 -1을 반복하자.
- 방법 요약
- 입력 변수(num)를 n(2~num)으로 나누고, 좌/우로 값을 번갈아 하나씩 연결시키며 더한다.(n 개수 만큼 연결)
- 더한 값이 num과 같으면 기록하고, 커지면 break한다.
- 반복하다가 왼쪽 값이 1이거나 오른쪽값이 num과 같아지면 그만한다.
#include<iostream>
#include<vector>
int main() {
#include<iostream>
#include<deque>
int main() {
int num;
scanf_s("%d", &num);
int cnt = 0;
int lIdx = 0, rIdx = 0;
int n = 2;
for (n = 2; n < num; n++) {
int sum = 0;
int mok = num / n;
std::deque<int> result;
bool flag = true;
lIdx = mok; rIdx = mok;
int kk = 1;
sum += mok;
result.push_back(mok);
while (kk < n) {
if(flag){
rIdx++;
sum += rIdx;
flag = false;
result.push_back(rIdx);
}
else {
lIdx--;
sum += lIdx;
flag = true;
result.push_front(lIdx);
}
kk++;
if (sum > num) break;
else if (sum == num) {
std::cout << result[0];
for (int ii = 1; ii < result.size(); ii++) {
std::cout << " + " << result[ii];
}
std::cout << " = " << sum << std::endl;
cnt++;
}
if (lIdx == 1 || rIdx == num) break;
}
}
std::cout << cnt;
return 0;
}예시
- 입력 : 15
- 2로 나누어질 경우
- 15 / 2 = 7 => 오른쪽하나 증가하여 8 , ==> {7,8}
- 15 / 3 = 5 => 오른쪽하나 증가 6, 왼쪽하나 증가 4, ==> {4,5,6}
- 15 / 4 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5 ==> 2+3+4+5 != 15 이므로 (x)
- 15 / 5 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5, 왼쪽 하나 증가 1 ==> {1,2,3,4,5}
- lIdx가 1이므로 멈춤
2. 풀이2 : n이 연속된 2개로 분리된다면, n에서 1,2 를 뺀값을 2로 나누어 떨어진다.
- 방법 요약
- n = 2일 경우, 15 에서 1,2를 뺀 12를 2로 나누어 떨어진다.
- 1,2에 12/2의 몫 6을 각각 더해주면 된다. ( 7,8 )
- n = 3일 경우, 15에서 1,2,3을 뺀 9를 3으로 나누어 떨어진다.
- 1,2,3에 9/3의 몫 3를 각각 더한다. (4,5,6)
- 반복한다.
int main() {
#include<iostream>
using namespace std;
int main() {
int a, b = 1, cnt = 0, tmp, i;
scanf_s("%d", &a);
tmp = a;
a--;
while (a > 0) {
b++;
a = 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\n", cnt);
return 0;
}예시
- 입력 : 15
- n : 2일 경우
- 15 에서 1,2를 뺀 12 / 2 는 나머지가 0이므로 1,2에 6을 더한 값이 정답 => {7,8}
- n : 3일 경우
- 15 에서 1,2,3를 뺀 9 / 3 은 나머지가 0이므로 1,2,3에 3을 더한 값이 정답 => {4,5,6}
- 15 에서 1,2,3,4를 뺀 5 / 4 은 나머지가 1이므로 pass
- 15에서 1,2,3,4,5를 뺀 0 / 5 는 나머지가 0이므로 1,2,3,4,5에 0을 더한 값이 정답 => {1,2,3,4,5}
- a가 0이므로 멈추고 개수 출력
참고
반응형