[백준] 5624번. 좋은 수

[문제]

 

www.acmicpc.net/problem/5624

5624번: 좋은 수

[풀이]

 

N개의 수열이 입력으로 주어지고, 하나의 숫자가 앞의 3개의 숫자를 더해서 나타낼 수 있을 때 좋은 수라고 한다.

이 때 입력에서 좋은 수의 갯수를 구해서 출력하면 된다.

 

좋은 수인지 판단하려는 숫자고 D라고 하면 A+B+C=D를 만족하는 수를 찾으면 된다.

좀더 다르게 생각하면 A+B=D-C 를 만족하는 D를 찾으면 된다.

 

따라서 D 이전의 숫자들 중에서 A+B의 값을 negative, positive 배열에 저장해놓고

D-C를 만족하는 값이 있는지 확인하는 방법으로 구현했다.

 

입력으로 주어지는 숫자가 -100,000 ≤ Ai ≤ 100,000이므로 A+B가 음수일수도 있다.

음수는 negative 배열에, 양수는 positive 배열에 저장했다.

 

 

[코드]

 

시간 : 8ms

 

#include <iostream>
#define MAX 100001

using namespace std;

int N;
int arr[5001]={0,};
bool positive[MAX*2]={0,};
bool negative[MAX*2]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    
    int cnt =0;
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            int num =arr[j]+arr[i-1];
            if(num >=0) positive[num]=true;
            else    negative[num*-1]=true;
        }

        for(int j=0;j<i;j++){
            int num =arr[i]-arr[j];
            if(num >=0 && positive[num]){
                cnt++;
                break;
            }
            else if( num<0 && negative[num*-1]){
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
    return 0;
}