[백준][1549번][수학] K

K

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

<코드>

#include <stdio.h>
#include <algorithm>
#include <climits>
 
using namespace std;
 
struct indexValue{
    long long value;
    int index;
 
};
 
long long A[4005];
indexValue B[4005]; //0 은 값어치 1은 인덱스 값 저장할 곳
long long minA[2] = { LONG_MAX, 0 };
 
 
long long ABS(long long a)
{
    return a > 0 ? a : -a;
}
 
bool cmp(const indexValue &u, const indexValue &v) {
    if (u.value < v.value) return true;
    else
        return false;
}
 
int main(void){
    int size;
    long long k;
    bool zero = false;
    scanf("%d", &size);
 
    for (int i = 0; i < size; i++)
        scanf("%lld", &A[i]);
 
    for (k = size / 2; k > 0; k--){
        indexValue temp;
        temp.value = A[0];
        temp.index = 0;
        B[0] = temp;
 
        for (int i = 1; i < size; i++)
        {
            indexValue tempPri = B[i - 1];
            temp.index = i;
            if (i < k)
                temp.value = tempPri.value + A[i];
            else
                temp.value = tempPri.value + A[i] - A[i - k];
 
            B[i] = temp;
        }
 
        sort(B + k - 1, B + size, cmp);
 
        for (int i = k - 1; i < size; i++)
        {
            for (int j = i + 1; j<size; j++){
 
                long long haha = ABS(indexValue(B[i]).value - indexValue(B[i + 1]).value);
                if (ABS(indexValue(B[i]).value - indexValue(B[j]).value) != haha)
                    break;
 
                if (ABS(indexValue(B[i]).index - indexValue(B[j]).index) >= k)
                {
                    if (minA[0] >ABS(indexValue(B[i]).value - indexValue(B[j]).value))
                    {
 
                        minA[0] = ABS(indexValue(B[i]).value - indexValue(B[j]).value);
                        minA[1] = k;
 
                    }
 
                    if (ABS(indexValue(B[i]).value - indexValue(B[j]).value) == 0)
                    {
                        zero = true;
                        break;
                    }
                }
 
            }
            if (zero == true)               break;
 
 
        }
        if (zero == true)
            break;
    }
 
    printf("%lld\n%lld\n", minA[1], minA[0]);
 
    return 0;
}

<문제 푼 요령>

 1. 예를 들어 5개의 합을 구하는 것을 구할려면 미리 5개의 합을 알려주는 배열을 구한다.

 2. 이 합을 구한것에 저장되어야 할 것은 index 와 합의 value 값이다.

 3. 이 합을 더해진 배열을 오름차순 정렬한다.

 4. 그래서 인접한 행렬끼리 나오는 min 값을 찾아서 갱신해준다. 단 min값의 갱신 조건의 index는 ABS(j-i)>=k 이다.

 5. min 값이 0 이면 검색을 멈춘다.

 6. 이 과정을 k/2 부터 1 까지 진행한다. 그래서 0 아니면 가장 끝에 나오는게 최소가 된다.

<배운 것>

 1. <algorithm> 의 sort 사용법을 알게됨 -> 최적의 정렬을 해준다고 함

 2. <climits> 의 편리함 이걸로 각 자료형의 최대치를 쉽게 표현 가능 -> 이걸 안해줘서 문제가 많이 일어남