글 읽기 - 탑다운 방식으로 시간초과 원인 알수 있을까요?

revolution_2 5년 전 0

탑 다운 방식으로 문제를 접근했는데 계속 시간 초과가 나는데 원인을 알수 있을까요?

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, k;
int dp[10001];
int money[101];

int dfs(int sum, int cnt) {
    // 구하려는 k보다 클 경우 그냥 리턴
    if(sum > k) {
        return 987654321;
    }
    // dp의 값이 초기값이 아닌 데이터가 저장되어 있고 현재보다 cnt보다 숫자가 작으면 리턴
    if(dp[sum] != 987654321 && dp[sum] > 0 && cnt > dp[sum]) {
        return dp[sum];
    }
    // 합계가 같으면 경우의 수 리턴
    if(sum == k) {
        return cnt;
    }

    int ans = 987654321;
    for(int i = 0; i < n; i ++) {
        ans = min(ans, dfs(sum+money[i], cnt+1));
    }

    dp[sum] = ans;
    return dp[sum];
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &money[i]);
    }
    // 디피 배열 초기화
    memset(dp, -1, sizeof(dp));
    int ans = dfs(0, 0);
    printf("%d", ans == 987654321? -1 : ans);
    return 0;
}

djm03178 5년 전 0

값을 구해놨는데 또 바뀔 수 있으니 제대로 dp를 했다고 볼 수 없습니다.

2 99

revolution_2 5년 전 0

답변 달아주셔서 감사합니다!

답변주신대로 모든 경우를 다해보고 답이 안나오는경우 -1을 구하는 과정에서 시간초과가 나오는 것 같네요.

기존 코드를 활용하면서 어떤식으로 변경이 가능할까요?? 아무리 고민해도 dpㅇㅔ 저장할때 또는 출력할때 예외를 해줘야 할것같은데 많이 어렵네요 ㅠ

if(dp[sum] > 0 && cnt > dp[sum]) {
        return dp[sum];
}

djm03178 5년 전 1

동전을 사용하는 순서를 정해서 해보세요. i번째 동전을 0개 쓰는 것, 1개 쓰는 것, 2개 쓰는 것을 순차적으로 다 해본 뒤에 i+1번째 동전으로 넘어가는 식으로요.

revolution_2 5년 전 0

다음과 같은 방식으로 문제를 풀었습니다!!

답변 진심으로 감사합니다!!

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, k;
int dp[10001];
int money[101];

int dfs(int sum, int cnt) {
    if(sum > k) {
        return 987654321;
    }
    if(dp[sum] != -1) {
        return dp[sum];
    }
    if(sum == k) {
        return 0;
    }
    
    dp[sum] = 987654321;

    for(int i = 0; i < n; i ++) {
        dp[sum] = min(dp[sum], dfs(sum+money[i], cnt+1) + 1);
    }

    return dp[sum];
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &money[i]);
    }
    memset(dp, -1, sizeof(dp));
    int ans = dfs(0, 0);
    printf("%d", ans == 987654321? -1 : ans);
    return 0;
}

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

문제

문제

출처

ICPC

탑다운 방식으로 시간초과 원인 알수 있을까요?

revolution_2 5년 전 0

djm03178 5년 전 0

revolution_2 5년 전 0

djm03178 5년 전 1

revolution_2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말