[5624] 좋은 수

좋은 수 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	616	209	165	35.256%

문제

정수 N개로 이루어진 수열 A가 있다. 이 때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제 입력 

6
1 2 3 5 7 10

예제 출력 

4

힌트

이 문제는 A + B + C = D를 찾는 문제입니다.

그렇다고 N^3을 하기에는 N이 5000까지입니다.

 

이 문제의 포인트는 2가지입니다.

 

1.  A + B = D - C 로 식을 변형한다.

2. Ai의 범위가 -10^5 ~ 10^5라는 점.

풀이 방법은 1번과 2번을 이용하면 A + B의 범위가 -2 * 10 ^5 ~ 2 * 10^5라는 것을 알 수 있습니다.저게 핵심입니다. 

저만큼의 배열을 선언해서 0부터 20만까지는 -범위 20만부터 40만까지는 + 범위입니다.

이제부터 두가지 풀이법에 대해서 설명해드리겠습니다.

1번 풀이는 i포문을 돌 때 해당 i 전까지 if(ab[data[i] - data[j] + MAX_VALUE])가 존재하는 지 검사한다.

이 말은 d - c가 존재하는지 검사합니다.

그리고 존재하면 좋은 수이므로 ret을 증가시킵니다.

 

for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;

이 코드는 a+b를 존재한다고 표시해줍니다. 이 과정을 반복합니다.

 

아래의 코드입니다.

#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_VALUE 200000
 
int data[MAX_SIZE];
bool ab[MAX_VALUE * 2];
 
int main()
{
 
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(ab[data[i] - data[j] + MAX_VALUE])
            {
                ret++;
                break;
            }
        }
 
        for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;
    }
 
    printf("%d\n", ret);
 
    return 0;
}
 

아래는 2번 풀이입니다.

이 풀이는 가능한 a+b를 테이블에 다 저장합니다.

위의 풀이와 다른점은 인덱스를 저장한다는 점입니다.

a+b가 검사하는 d 이후에 만들어졌다면 사용할 수 없는 a + b이기 때문입니다.

 

if(tmp != -1 && tmp < i)를 이용해서 -1이면 a + b = d - c 를 만족하지 않으므로 좋은 수가 아니고

tmp >= i 라면 나의 인덱스보다 이후에 만들어진 수이므로 좋은 수가 아닙니다.

#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_TABLE 400002
 
int n;
int data[MAX_SIZE];
int table[MAX_TABLE];
 
int main()
{
    memset(table, -1, sizeof(table));
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            int sum = data[i] + data[j];
            int& tmp = table[200000 + sum];
            if(tmp == -1) tmp = i;
        }
    }
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            int diff = data[i] - data[j];
            int& tmp = table[200000 + diff];
            if(tmp != -1 && tmp < i)
            {
                ret++;
                break;
            }
        }
    }
 
    printf("%d\n", ret);
    return 0;
}