글 읽기 - 시간초과가 나는 이유를 알려주세요

joonbo97 3년 전 0

dp를 이용하여 해결하긴 하였는데, 아래의 코드가 시간초과가 나는 이유를 모르겠습니다.

아래의 코드도 O(N^2)이고, dp로 풀어도 O(N^2)아닌가요?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int max = 0;

void cal(int* arr,int now_idx ,int total, int price)
{
    int card_pack_cnt;

    if (now_idx == 1 || total == 0)
    {
        price += total * arr[1];
        if (price > max)
            max = price;
    }
    else
    {
        card_pack_cnt = total / now_idx;
        for (int j = 0; j <= card_pack_cnt; j++)
            cal(arr, now_idx - 1, total - j * now_idx, price + j * arr[now_idx]);
    }
}

int compare(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int main() {
    int N;//total = 우리가 원하는 카드의 개수
    scanf("%d", &N);

    int* arr = (int*)malloc(sizeof(int) * (N + 1));
    for (int i = 1; i <= N; i++)
        scanf("%d", &arr[i]);

    int* dp = (int*)malloc(sizeof(int) * (N + 1));

    dp[0] = 0;


    /*for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] = compare(dp[i], dp[i - j] + arr[j]);
            
        }
        
    }*/
    cal(arr, N, N, 0);
    printf("%d", max);
    
}

jjang36524 3년 전 1

이 코드는 다항 시간이 아닙니다. 같은 연산을 중복해서 하기 때문입니다.

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

문제

문제

출처

ICPC

시간초과가 나는 이유를 알려주세요

joonbo97 3년 전 0

jjang36524 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말