[백준] 5624번 좋은 수 (C++)

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

 

 

이 문제는 수열이 주어졌을때 하나의 원소를 잡고 앞에서 중복포함한 3개의 수를 더하여 원소의 값을 나타낼 수 있는 경우 좋은 수라고 표현할때 이 좋은 수의 개수를 출력하는 문제이다.

 

수열의 크기는 최대 5000으로 모든경우를 처음부터 찾는 경우 O(N^3)으로 시간초과가 난다. 따라서 

찾은 수에 대해서 방문체크를하여 저장(memozation)을 사용하여 시간을 단축해야한다.

 

 

즉 어떤 원소 A[i]라고 표현하면

A[i] = A[j] + A[k] + A[l]로 표현할 수 있다 이때 j, k, l은 같은 수를 허용한다.

 

이때 하나의 수를 좌변으로 넘기면 A[i] - A[j] = A[k] + A[l]로 표현할 수 있다.

 

그렇다면 3개의 수의 합을 A[i] - A[j]로 표현할 수 있기 때문에 저 값을 구하여 존재하는지 체크하면 된다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
int arr[5001];
bool visited[400001];

void solve() {
    int answer = 0;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(visited[arr[i] - arr[j]+ 200000]) {		// A[i] - A[j]가 있는 경우
                answer++;
                break;
            }
        }

        for(int j = 0; j <= i; j++) {				
            visited[arr[i] + arr[j] + 200000] = true;
        }
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

식을 변형하는 생각을 하지 못했다면 풀기 어려웠던 문제이다. 나도 처음엔 앞에 중복된 3개를 더해야해서 dp인거같은데

어떻게 풀어야할지 생각이 안나서 결국 구글링을 했던 문제...