koitp 세금(TAX)(C++)

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.5 초	512 MB	1073	64 (6%)	38

문제

납세의 의무는 국민의 기본적인 의무이다. 세금은 수입에 비례하여 정해진 규칙에 따라 계산되기 때문에, 규칙에 따라서 정확한 수입을 계산하는 것이 중요하다. 여러분은 새로 가게를 열고, 총 N 일 동안 영업을 하였다. 납세의 의무를 성실하게 수행하기 위하여 매 영업일마다 손익(이익 또는 손해)을 기록하여 세무서에 신고하였다. 세금을 매기는데 기준이 되는 수입은 다음 규칙에 의해서 계산된다.

"1일부터 N일 사이의 어떤 연속된 기간에 대하여 이 기간 동안 손익의 총합을 구한다. 단, 하루 이상의 기간만 고려한다. 다음, 전체 가능한 모든 기간에 대하여 구한 손익의 총합들 중 K번째로 큰 값이 기준이 된다. 즉, 총합들을 내림차순으로 정렬했을 때 K번째 값이다."

예를 들어, 총 3일간 영업을 하였다면 1일, 1일~2일, 1일~3일, 2일, 2일~3일, 3일 총 6가지 기 간에 대하여 각 기간마다 손익의 총합을 구하고, 이 중 K번째 큰 값이 세금의 기준이 된다.

입력

첫 번째 줄에는 N과 K가 사이에 하나의 공백을 두고 주어진다. 단, 1≤N≤1,000,000, 1≤K≤min(50, N(N+1)/2) 이다.

다음 줄에는 매 영업일의 손익을 나타내는 N개의 정수가 사이에 하나 의 공백을 두고 주어진다. 만약 해당 영업일에 이익을 보았다면 양의 값, 손해를 보았다면 음의 값, 이익 손해 모두 없다면 0이다. 손익의 범위는 -1,000,000,000 부터 1,000,000,000 사이이다.

출력

조건을 만족하는 손익의 총합이 K번째로 큰 값을 나타내는 하나의 정수를 출력한다.

힌트

입력 예제

4 3
20 -10 10 5

출력 예제

20

#include    <cstdio>
#include    <algorithm>
#include    <queue>
#include    <functional>
#include    <vector>
#pragma warning(disable:4996)
 
long long int D[1111111][55];
long long int n[1111111];
 
std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int>> res;
bool comp(long long int a, long long int b){ return a > b; }
int main(void){
 
    int N, K;
    scanf("%d%d", &N, &K);
 
    for (int i = 1; i <= N; ++i)
        scanf("%lld", &n[i]);
 
    D[1][1] = n[1];
    res.push(D[1][1]);
    K++;
    for (int i = 2; i <= N; ++i)
    {
        D[i][1] = std::max(D[i - 1][1], (long long int)0) + n[i];
        D[i][2] = std::min(D[i - 1][1], (long long int)0) + n[i];
         
        for (int j = 3; j <= (i / K > 0 ? K : i%K); ++j)
        {
            D[i][j] = D[i - 1][j - 1] + n[i];
        }
 
        for (int j = 2; j < (i / K > 0 ? K : i%K); ++j)
        {
            if (D[i][j] < D[i][j + 1])
                std::swap(D[i][j], D[i][j + 1]);
        }
    }
    K--;
    for (int i = 1; i <= N; ++i)
    {
        if (res.size() == K && D[i][1] < res.top())
            continue;
        for (int z = 1; z <= (i / K > 0 ? K : i%K); ++z)
        {
            if (res.size() < K)
                res.push(D[i][z]);
            else if (res.top() < D[i][z])
            {
                res.pop();
                res.push(D[i][z]);
            }
        }
    }
    printf("%lld\n", res.top());
}

dynamic programing

연속된 수에서 k번째 가장 큰 수를 찾는 문제이다.

priority queue(heap)을 이용하여 풀었다. 

사실 이게 맞는 답인지는 모르겠지만 우선은 해당 사이트에서는 100점으로 통과를 했다.. 

(1.5초 제한에 가장 길게 나온게 1.2초나 되서 최적화를 더 할 수 있을 것 같기는 하다.)

k번째 최단경로를 푼 후부터 k번째 큰/ k번째 작은 같은 문제가 나오면 뭔가 힙을 이용해야 할 것 같은 느낌이 들기 시작했다... 

이 문제는 두 가지를 생각하면 풀린다. 

1. i번째까지, i를 포함하는 가장 큰 부분합은 D[i][1]이라고 하였다.  

이때, D[i][1] = max(D[i-1][1], 0) + n[i]이다. 사실 이 공식은 약간 유명?까진 아니어도 가장 큰 부분합을 구하는 공식으로 사용된다. 

(사실 이렇게 구한 D[i][1]들 중에 가장 큰 D[x][1]이 전체 수열의 가장 큰 부분합이 된다. - D[i][1]은 i를 꼭 포함하는 가장 큰 부분합일 뿐.)

2. k번째 큰 부분합은 각 i번째를 포함한 k번째 큰 부분합들 중에 있다. 

i길이까지, i를 포함하는 k번째 큰 부분합은 D[i][k]라고 할 때 이는 max(D[i-1][k],0) + n[i]이 된다. 

이렇게 된다면 결국 

연산해야 할 것은 n개 날짜 중 k번째를 구하기 위해 n*k연산을 하면 된다. 

이후 모든 수를 min-heap에 넣어주어 top을 출력하였다. 

heap은 k개 이상 들어가지 않게 하였기 때문에 root가 결국 k번째로 큰 부분합이라고 할 수 있다.