글 읽기 - 재귀로 구현할 때 시간초과...?

blueahj88 1년 전 0

저에게 점화식보다 탑다운이 편한 접근이라 탑다운으로 해봤는데,

나름 dp로 구성했다고 생각했는데도 시간초과가 발생하네요...ㅠ

혹시 잘못된 부분이 있을까요?

#include <iostream>
#include <set>

#define LIMIT 10000

using namespace std;

int n, k;
set<int> coin;
int memo[LIMIT + 10];

int calc(int price) {
    int& ret = memo[price];
    if (price == 0) return 0;
    if (ret < LIMIT + 1)
        return ret;

    for (int c: coin) {
        if (price - c >= 0)
            ret = min(ret, calc(price - c) + 1);
    }

    return ret;
}

int main() {
    int ans;
    cin >> n >> k;

    for (int i = 1; i <= k; i++)
        memo[i] = LIMIT + 1;

    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        if (c > k) continue;
        coin.insert(c);
    }

    ans = calc(k);

    cout << (ans < LIMIT + 1 ? ans : -1) << endl;

    return 0;
}

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

문제

문제

출처

ICPC

재귀로 구현할 때 시간초과...?

blueahj88 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말