KOITP 큰수만들기

<링크>

https://koitp.org/problem/SDS_TEST_BIGINT/read/

<풀이>

처음에는 덧셈횟수와 뺄셈횟수를 이용해 dfs하여 풀었으나 시간초과가 떴다. 연산자의 수가 대략 100,000개니까

100,000!이면 굉장한 시간이다.

#include<stdio.h>
int N, P, M;
int card[100000];
long long ans;
void dfs(long long, int);
int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t)
    {
        scanf("%d%d%d", &N, &P, &M);
        for (int i = 0; i < N; ++i)
            scanf("%d", card + i);
        ans = -100000000000L;
        dfs(card[0], 1);
        printf("%lld\n", ans);
    }
}
void dfs(long long n, int len)
{
    if (len == N)
    {
        if (n > ans)
            ans = n;
        return;
    }
    if (P)
    {
        --P;
        dfs(n + card[len], len + 1);
        ++P;
    }
    if (M)
    {
        --M;
        dfs(n - card[len], len + 1);
        ++M;
    }
}

예전에 봤던 문제가 생각나서 나도모르게 이렇게 한 것같다.

2018/07/22 - [알고리즘 풀이/브루트 포스] - 백준 14888 연산자 끼워넣기 :: 들짐승

다시 생각해보니 덧셈은 최대한 큰 수들로만 하고

뺄셈은 최대한 작은 수들로만 하면 최대값이 나올 수 있단 걸 깨닳았다.

맨 앞의 카드만 고정시키고

뒤의 카드는 내림차순으로 정렬했다. 그 후 덧셈,뺄셈 순서대로 계산했다.

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;
int card[100000];
int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t)
    {
        
        int N, P, M;
        scanf("%d%d%d", &N, &P, &M);
        for (int i = 0; i < N; ++i)
            scanf("%d", card + i);
        sort(card + 1, card + N,greater<int>());
        long long ans = card[0];
        for (int i = 1; i <= P; ++i)
            ans += card[i];
        for (int i = 1 + P; i < N; ++i)
            ans -= card[i];
        printf("#%d %lld\n", t, ans);
    }
}