[2355번] 시그마

문제 출처 :

 

https://www.acmicpc.net/problem/2355

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

2. 연속된 수열의 합

이 코드의 함정은, signed int형이라고 하여 그대로 지정하면 안된다.

왜냐하면 (n-1)*n 같이 signed int의 경계선의 n이었다면 두수를 곱하면 signed int를 벗어나는 값이 도출되어 

값 도출에 오류가 생길것이다.

따라서 signed int의 범위를 넘어도 되는 long long int 혹은 long int를 이용하여 문제를 푸는 것이다.

하지만 이 코드도 signed int이상의 값을 요구할 때는 오버 플로우가 일어날 수 있다.

따라서 2번 코드를 이용하여 오버 플로우를 피할 수 있는 코드를 작성한다.

** 참고로 오버플로의 단적인 예는 다음과 같다. **

이진 탐색 알고리즘을 제작할 때 mid를 다음과 같이한다.

 mid = (first+last)/2; // 탐색 대상의 중앙을 검색

하지만 first와 last가 int의 한계인 2^32-1 인값이었다면 두수를 더하면 결국 int를 벗어나게 되어 

오버 플로우로 인해 mid가 찾아지지 않는다.

따라서 코드를 짤 때는 오버 플로우에 대한 생각도 해주어야 한다. 

즉, last + (first-last) / 2 이렇게 제작해 준다면 오버 플로우는 피할 수 있다.

소스 코드 : 

1번

#include <stdio.h>
 
long long int n;
long long int m;
long long int ans1, ans2;
 
int main()
{
 
    scanf("%lld %lld", &n, &m);
 
    if(n > m)
    {
        int tmp = n;
        n = m;
        m = tmp;
    }
    
    ans1 = ((n-1)*n) / 2;
    ans2 = (m*(m + 1)) / 2;
 
    printf("%lld", ans2 - ans1);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

2번

#include <stdio.h>
 
long long int n,m;
long long int tmp, mid, cnt;
long long int ans1, ans2;
 
int main()
{
 
    scanf("%lld %lld", &n, &m);
 
    if (n > m)
    {
        int tmp = n;
        n = m;
        m = tmp;
    }
 
    cnt = m - n + 1;
    if (cnt % 2 == 0)
    {
        tmp = n;
        n++;
        cnt--;
        mid = (n + m);
 
        printf("%lld",mid/2 * cnt + tmp);
    }
 
    else if (cnt % 2 == 1)
    {
        mid = (n + m);
 
        printf("%lld", mid/2 * cnt);
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>