백준 5624번 좋은 수

문제 링크입니다: https://www.acmicpc.net/problem/5624

A + B + C = D를 만족하는 D가 몇개 있는지를 물어보는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 문제를 A + B = D - C로 바꿉니다.

2. D - C가 존재하는지 확인하고 존재한다면 좋은 수가 있다는 뜻입니다.

3. 여태까지의 A + B를 표시합니다.

4. 2번과 3번을 반복합니다.

#include <iostream>

using namespace std;

 

const int MAX = 5000;

const int sumMAX = 400000; // -200,000 ~ 200,000

 

int A[MAX];

bool visited[sumMAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> A[i];

 

        int result = 0;

        //A + B + C = D

        //A + B = D - C

        for (int i = 0; i < N; i++)

        {

                 for (int j = 0; j < i; j++)

                 {

                         //D - C 존재 여부

                         if (visited[A[i] - A[j] + 200000])

                         {

                                 result++;

                                 break;

                         }

                 }

 

                 //A + B 표시

                 for (int j = 0; j <= i; j++)

                         visited[A[i] + A[j] + 200000] = true;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~