글 읽기 - 비슷한 문제 또는 풀이가 가능한 알고리즘을 알고 싶습니다.

rkdgh98 2년 전 0

모 테스트에서 나온 문제인데 시험동안 TLE를 해결 못하고 나와서 혹시 백준 사이트에서 해결해주실 분이 있을까 싶어 올립니다..

문제)

동전을 세 개만 투입하여 상품을 구매할 수 있는 자판기가 있다.
이 자판기는 가격이 딱 맞아야만 상품을 구매할 수 있다.

N개의 동전이 주어진다. 각 동전은 3개까지 사용할 수 있다.

M개의 상품 가격이 주어진다.

동전 세 개를 조합하여 살 수 있는 상품 중에 가장 싼 상품의 가격과 가장 비싼 상품의 가격을 출력하시오.

(1<=N,M<=700, 1<= 동전의 단위, 상품 가격 <= 1억)

제한시간 : C++ 1.5초

input
6 6
1 2 3 4 5 7
4 9 3 10 22 9
output
3 10

input
3 5
3 1 2
10 15 20 25 30
output
-1

input
3 1
1 2 3
9
output
9 9

저는 중복조합을 통한 O(MN^3) 밖에 생각나지 않아서 TLE를 해결하지 못하고 있습니다.

혹시 문제를 보고 생각나는 알고리즘이 있으시다면 알려주시면 좋겠습니다..

또는 백준에서 비슷한 문제를 보셨다면 추천해주신다면 무한한 감사드리겠습니다..

rhdqor213 2년 전 2

환경에 따라 다르지만 이분탐색을 이용한 O(N^3logM)이면 될것 같습니다.

또는 비트마스킹을 이용한다면 1억개의 비트로 상품의 유무를 체크해서 O(N^3)에도 가능해보입니다.

rkdgh98 2년 전 0

@rhdqor213

귀한 시간 내주시고 좋은 의견 주셔서 정말 감사드립니다.

죄송하지만 아직 궁금한 점이 있어서 추가적인 질문을 올리겠습니다.

N^3이면 700^3 이 3억 4천 정도 되는데, 이게 1.5초 안에 해결이 될까요?

그리고, 제가 글에는 언급을 안했지만, 추가적으로 문제에서 테스트케이스가 총 40개까지 주어진다고 나왔는데, 제 생각에 최악의 경우 100억까지도 되어서 1.5초 안에 해결이 안될 것 같습니다.

중복조합쪽에서 시간을 단축할 순 없는 걸까요?

shjohw12 2년 전 2

M개의 각 상품에 대해 N개의 동전 값을 빼서 NM개의 상품을 새로 만들어서 동전을 2개 쓴다고 생각하면 N^2 으로 되겠네요

rkdgh98 2년 전 0

@shjohw12

NM이 결국 N^2이라고 하면 이분탐색으로 2logN을 만들 수 있군요..

그럼 최종적으로 O(N^2 log N)이 나올 수 있겠네요.. 대박입니다

이해되었습니다 정말 감사드립니다

shjohw12 2년 전 2

심심해서 코드도 짜봤어요

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
#define int ll
#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;







signed main() {
#ifdef LOCAL
    freopen("debug.txt", "w", stderr);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(20);







    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    vector<pi> bb;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            bb.emplace_back(b[i] - a[j], b[i]);
        }
    }

    sort(all(bb));

    int mn = inf, mx = minf;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            auto it = lower_bound(all(bb), pi(a[i] + a[j], minf));

            if (it != bb.end() && it->first == a[i] + a[j]) {
                mn = min(mn, it->second);
                mx = max(mx, it->second);
            }

            it = lower_bound(all(bb), pi(a[i] + a[j], inf));

            if (it != bb.begin()) {
                --it;
                if (it->first == a[i] + a[j]) {
                    mn = min(mn, it->second);
                    mx = max(mx, it->second);
                }
            }

        }
    }

    if (mn == inf) {
        cout << -1 << '\n';
    }
    else {
        cout << mn << ' ' << mx << '\n';
    }


















    return 0;
}

제시하신 문제는 k-SUM이라고 부르는 컴퓨터과학의 대표적인 문제입니다. 이 경우는 k = 4이며 약간의 제약조건이 붙어 있지만, k-SUM을 해결하는 Meet in the Middle 알고리즘을 통해 동일하게 해결할 수 있습니다. 일반적으로 O(n^k/2)보다 이 문제를 빠르게 푸는 방법은 알려져 있지 않습니다만, 특수한 제약 조건이 붙으면(가격의 상한 등) 실용적으로는 더 빨리 해결할 수 있는 알고리즘(DP, FFT 등)이 존재합니다.

제시하신 문제의 제약조건을 풀 수 있는, 비슷한 아이디어를 사용하는 문제는 solved.ac에 아주 많습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

비슷한 문제 또는 풀이가 가능한 알고리즘을 알고 싶습니다.

rkdgh98 2년 전 0

rhdqor213 2년 전 2

rkdgh98 2년 전 0

shjohw12 2년 전 2

rkdgh98 2년 전 0

shjohw12 2년 전 2

kipa00 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말