티스토리 뷰

알고리즘 관련/BOJ

BOJ)5624 좋은 수

JASON 자손9319 2017. 5. 17. 22:24

문제:icpc.me/5624


좋은 수의 조건은 나보다 먼저 들어온 수 i, j ,k 의 합이 나와 같은 경우가 존재하는 경우이다.


우리는 이 수식을 i+j+k=x 로 생각할 수 있고 이 수식을 i+j=x-k로 바꿔 생각할 수 있다.


그러면 우리는 x를 받기전에 들어온 모든 수들의 합의 셋(i+j)들을 배열로 저장하여 O(1)만에 존재하는지 확인할 수 있다.


고로 모든 x-k에 대하여 같은 i+j가 존재하는지 확인해 준다면 O(N^2)에 문제를 해결할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
#define mid 200000
using namespace std;
int a[5010], n, b[400040], res;
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++)
        scanf("%d"&a[i]);
    for (int i = 0; i < n; i++) {
        int here = a[i];
        for (int j = 0; j < i; j++) {
            if (b[here - a[j] + mid]) {
                res++;
                break;
            }
        }
        for (int j = 0; j <= i; j++)
            b[here + a[j] + mid] = 1;
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2254 감옥 건설  (0) 2017.06.01
BOJ)5670 휴대폰 자판  (0) 2017.05.30
BOJ)5624 좋은 수  (0) 2017.05.17
BOJ)12961 체스판2  (0) 2017.05.17
BOJ)3654 L퍼즐  (0) 2017.05.17
BOJ)13308 주유소  (0) 2017.05.04
댓글
댓글쓰기 폼