[코드그라운드] 연습문제 좋은수

>> 문제 설명

이 문제를 해결할 때 3가지의 숫자의 조합을 얻을 수는 없다. 해결 방법은 P+Q+R = S 의 식을 P + Q = S - R로 변형해서 풀면 된다. 

두가지의 숫자의 합을 저장할 배열 (크기 400001, 0번째는 안씀) 을 사용해서 입력받은 집합들의 범위 내에서 (최대 숫자 범위 -100000 ~ 100000) 차례대로 두가지의 숫자를 더한 값을 배열에 저장한다. 

숫자들의 합은 음수 까지 생각해서 -200000 ~ 200000 범위라서 배열이 400000을 선언되야 된다.

N번째의 숫자 까지 저장했다면 N+1의 숫자의 좋은수를 검사할 때 1~N 의 배열을 이용해서 [N+1] - [1 to N] 을 사용해서 문제를 풀 수 있다.

>>작성한 코드

#include <stdio.h>
 
int Answer;
 
int main(void)
{
    int T, test_case;
    setbuf(stdout, NULL);
 
    scanf("%d", &T);
    for(test_case = 0; test_case < T; test_case++)
    {
        Answer = 0;
        int n;
        scanf("%d", &n);
 
        int arr[n];
        int arr2[400001] = {0};
        int i, j, k;
        
        for(i=0; i<n; i++){
            scanf("%d", &arr[i]);
        }
        
        for(i=0; i<n-1; i++){
            for(j=0; j<=i; j++){
                    arr2[arr[i]+arr[j]+200000] = 1;
            }
            
            for(k=0; k<=i; k++){
                if(arr2[arr[i+1]-arr[k]+200000]==1){
                    Answer++;
                    break;
                }
            }
        }
        
        printf("Case #%d\n", test_case+1);
        printf("%d\n", Answer);
        
    }
 
    return 0;//Your program should return 0 on normal termination.
}