Goal

투포인터 알고리즈즘을 C언어로 구현할 수 있다.

문제

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

만약 N = 15 dlaus
7 + 8 = 15
4 + 5 + 6 + 15
1 + 2 + 3 + 4 + 5 = 15
와 같이 총 3가지의 경우가 존재 한다.

입력설명

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

출력설명

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

설명

첫번째 방법은 투포인터 알고리즘을 사용하는 방법이 있다.

  1. Last = (N/2) + 1
  2. Left포인터, Right포인터는 0부터 시작을 한다.
  3. Right포인터에 위치한 값을 Sum에 더하기 한다.
  4. Sum의 값이 N보다 작으면, Right 포인터를 오른쪽으로 한칸 이동 한다.
  5. Sum의 값이 N과 같으면, count를 1 증가
  6. sum에서 Left에 위치한 값을 뺄셈 하고, Left를 오른쪽으로 한칸 이동 한다.
  7. Sum이 N보다 크면, sum에서 Left값을 빼고, Left를 오른쪽으로 한칸 이동 한다.
  8. Right값이 Last보다 크지않을때까지 위의 과정을 반복 한다.

두번째 방법은 수리를 사용하는 방법 이다.

  1. 15 에서 1과 2를 뺄셈한다. (15 - (1 + 2) = 12)
  2. 12 를 2로 나누면 몫이 6이고 나머지는 0 이다.
  3. (1+6) + (2+6) = 7 + 8 = 15 이다.
  4. 15에서 1,2,3,을 뺄셈한다. (15 - (1 + 2 + 3) = 9)
  5. 9를 3으로 나누면 몫이 3이고 나머지는 0 이다.
  6. (1 + 3) + (2 + 3) + (3 + 3) = 4 + 5 + 6 = 15 이다.
  7. 15에서 1,2,3,4,를 뺄셈 (5)
  8. 5을 4로 나누면 나머지가 0이 아니다. (4개의 연속된 수로 15 만들어지지 않음)
  9. 15에서 1,2,3,4,5를 뺄셈 (15)
  10. 0 을 0으로 나누면 몫이 0 이다.
  11. (1+0)+(2+0)+(3+0)+(4+0)+(5+0) = 1 + 2 + 3 + 4 + 5 = 15 이다.

코드

투포인터 알고리즘 적용

#include <stdio.h>
#include <vector>
using namespace std;
int main() {

    int i,left = 0, right = 0,last, n,sum = 0,count = 0;
    scanf("%d",&n);
    vector<int> num(n);
    last = (n / 2) + 1;
    for(i = 0; i < last; i++) num[i] = i+1; 
    while(right <= last) {

        if(sum == n) {
            printf("%d ",num[left]);
            for(i = left+1; i < right; i++) {
                printf("+ %d ",num[i]);    
            }
            count++;
            sum -= num[left];
            left++;
            printf("= 15 \n");
        }
        else if(sum < n){
            sum += num[right];
            right++;
        } 
        else if(sum > n) {
            sum -= num[left];
            left++;    
        }
    }
    printf("%d",count);

    return 0;
}

수리지식 이용

#include <stdio.h>

int main() {

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

    return 0;
}