연속수 (연이은 수의 합)

[별은빛나고]

카드가 있다. 보통 연속으로 숫자가 나오는 경우를 스트레이트라고 한다.

1부터 N까지의 숫자가 있다고 할때 그 사이에 있는 M이라는 숫자를 만들기 위해

스트레이트 갯수중 큰 값을 구하는 c언어 코드를 원합니다.

(항상 순차적으로 정렬이 되어 있다고 가정)

예1 : 1,2,3,4,5,6,7,8,9,10이라는 연속된 숫자 값이 주어졌다면 N=10이고 M=9를 만들기 위한 연속된 스트레이트 조합은

2,3,4와 4,5가 있고 해는 2,3,4의 갯수인 3이 나와야 함.

답:

1번이 맨 첫 수부터 1씩 더해서 합을 찾아가는데 

수를 찾았으면 첫 수를 이전에 탐색한 수 다음부터 1을 더해 다시 합을 구해 찾으므로 속도는 조금 늦습니다.

2번은 1번을 개선한 것으로 이미 찾은 합을 이용하여 앞 수를 빼고 뒷 수를 더하는 방법으로 연산 횟수를 줄였습니다.

가장 적은 갯수의 수로 된 것(큰 수들의 집합) 하나만을 찾을 때는 뒤에서 부터 찾으므로 3번이 확실히 빠릅니다.

4번은 3번을 1번처럼 이미 구한 합을 이용하도록 개선한 것입니다.

1.

/*--------------------------------------------------+ |_________가장 많은 갯수부터 나타낸 연속수__________|           +---------------------------------------------------*/  #include <stdio.h>   int main() {     unsigned int start = 1, end, num;     unsigned int i, sum, ruler = 2;          printf("합은 : ");      scanf("%d", &num);          end = num;            while (ruler <= num) {         if (num / ruler == 1 && num % ruler == 0) {             printf("연속수가 없습니다.\n");             return 0;         }         ruler <<= 1;    // ruler *= 2;     }                    // 2의 누승은 연속수가 없음           while (start < end) {         sum = 0;         for (i = start; i < end; i++) {             sum += i;               if (sum == num) {                 printf("%d ~ %d, %d장\n", start, i, i - start + 1); //                return 0;             }             else if (sum > num) {                 break;             }         }         start++;     }           return 0; } Colored by Color Scripter

cs

76.72초 걸림

2.

/*--------------------------------------------------+ |____이미 찾은 합을 이용하여 앞 뒤 수만 연산________|           +---------------------------------------------------*/  #include <stdio.h>   int main() {     unsigned int start = 1, end, num;     unsigned int i, sum, ruler = 2;          printf("합은 : ");      scanf("%d", &num);          end = num;            while (ruler <= num) {         if (num / ruler == 1 && num % ruler == 0) {             printf("연속수가 없습니다.\n");             return 0;         }         ruler <<= 1;    // ruler *= 2;     }                    // 2의 누승은 연속수가 없음    // 첫번째 것을 찾음         sum = 0;     for (end = start; sum < num; end++)    sum += end;     end--;          while (start < num) {         if (sum == num) {    // 찾았으면 다음을 위해 마지막 수를 뒤로 이동              printf("%d ~ %d, %d장\n", start, end, end - start + 1);             end++;             sum += end;         }         else if (sum > num) {    // sum이 크면 첫 수를 뒤로 이동              sum -= start;             start++;         }         else if (sum < num) {    // sum이 작으면 마지막 수를 뒤로 이동              end++;             sum += end;         }    }           return 0; } Colored by Color Scripter

cs

13.67초로 개선됨

3. 뒤부터 찾음(가장 큰 수들의 집합, 가장 적은 갯수의 집합)

/*--------------------------------------------------+ |_________가장 적은 갯수부터 나타낸  연속수_________|           +---------------------------------------------------*/  #include <stdio.h>   int main() {     unsigned int start = 1, end, num;     unsigned int i, sum, ruler = 2;          printf("합은 : ");      scanf("%d", &num);          end = num;       while (ruler <= num) {         if (num / ruler == 1 && num % ruler == 0) {             printf("연속수가 없습니다.\n");             return 0;         }         ruler <<= 1;    // ruler *= 2;     }                    // 2의 누승은 연속수가 없음            end = num / 2;        // 마지막 값      if (num % 2) end++;    // 홀수면 +1      start = end - 1;    // 시작값        while (start > 0) {         sum = 0;         for (i = start; i <= end; i++) {             sum += i;             if (sum == num) {                 printf("%d ~ %d, %d장\n", start, i, i - start + 1);                 end--; //                return 0;             }         }           if (sum > num)     end--;         if (sum < num)    start--;     }           return 0; } Colored by Color Scripter

cs

128.1초 걸림

4. 3번을 개선(이미 찾은 합을 이용하여)

/*--------------------------------------------------+ |____이미 찾은 합을 이용하여 앞 뒤 수만 연산________|           +---------------------------------------------------*/  #include <stdio.h>   int main() {     unsigned __int64 start = 1, end, num;     unsigned __int64 i, sum = 0, ruler = 2;          printf("합은 : ");      scanf("%d", &num);          end = num;       while (ruler <= num) {         if (num / ruler == 1 && num % ruler == 0) {             printf("연속수가 없습니다.\n");             return 0;         }         ruler <<= 1;    // ruler *= 2;     }                    // 2의 누승은 연속수가 없음            end = num / 2;        // 마지막 값      if (num % 2) end++;    // 홀수면 +1        for (start = end; sum < num; start--)    sum += start;     start++;        // 하나가 더 작아진 조건에서 탈출했으므로 복귀        while (start > 0) {         if (sum == num) {             printf("%lld ~ %lld, %lld장\n", start, end, end - start + 1);             sum -= end;        // 다음을 위해 좌로 전진 하려면 마지막을 빼줌              end--;            // 좌로 전진  //            return 0;        // 하나만 찾고 종료하려면          }         else if (sum > num)    sum -= end--;         else if (sum < num) sum += --start;     }           return 0; }   Colored by Color Scripter

cs

9.488초로 개선

위 코드들을 num / 2 + 1 범위로 좁히면 비교할 필요없는 뒷 부분을 생략함으로써 더 짧은 시간을 기대할 수 있습니다.