[dovelet][수학] 삼각형 만들기 / triangle1

dovelet    29 단계 수학    

삼각형 만들기 / triangle1

 

http://59.23.113.171/30stair/triangle1/triangle1.php?pname=triangle1

#include <stdio.h>
 
long long check[51000];
 
int main(void)
{
    int n, cnt = 0;
    scanf("%d", &n);
 
    int a, b, c;
 
    for (a = 1; a <= n / 3; a++)    {
        for (b = a; (b <= n / 2) && b <= (n - a - b); b++)    {
            c = n - a - b;
            if (a + b > c)    {
                cnt++;
            }
        }
    }
 
    printf("%d\n", cnt);
    return 0;
}

 

처음에 일단 모든 경우를 만들고 그안에서 조건을 걸어서 맞는 경우만 세도록 하였는데

그 방식은 당연하게도 time limit에 걸렸다.

그래서 종이에 하나하나 삼각형이 만들어지는 수를 적으면서 애초에 중복되는 경우를

없애도록 반복문의 범위를 줄여 time 성능을 늘림 

a를 세 변 중 가장 짧은 변으로 잡았기 때문에 1부터 n / 3까지 반복하였다.

그 후 b는 가장 짧은 변이 아니기 때문에 a와 같거나 큰 수로 가정하였고

또한 가장 큰 변을 c로 잡았기 때문에 b는 c에 해당하는 값보다 작도록 하여 반복하였다.