글 읽기 - 런타임에러 질문입니다..!

skcrabbit 6년 전 0

열심히 코드를 짰는데 런타임 에러가 떠부렸네요ㅜ

재귀적으로 짰지만 memoization 썻구요

정답은 잘 나옵니다.

한번 봐주시면 감사하겠습니다!

#include <stdio.h>
#include <stdlib.h>

int b_num, res_num;
int goalnum;
int tim;

int getMakingTime(int parent,int ridx, int* t_req_time, int* t_res, int* t_maketime);

int main(){
    
    int test_cnt;
    
    scanf("%d",&test_cnt);
    
    for(int i=0; i<test_cnt;i++){
        //소요시간
        int* req_time;
        
        //제한조건
        int* res;
        
        //건물 짓는 시간을 구했다면 미리 저장(dynamic programming)
        int* maketime;
        int result;
        
        //건물 개수와 제한조건 개수 입력
        scanf("%d %d",&b_num,&res_num);
        
        //동적배열 선언
        req_time = (int*)malloc(sizeof(int)*b_num);
        res = (int*)malloc(sizeof(int)*res_num*2);
        maketime = (int*)malloc(sizeof(int)*b_num);
        
        //maketime 초기화
        memset(maketime,0,sizeof(int)*b_num);
        
        //res[0] = 0;
        
        // 소요시간 입력받기
        for(int i=1; i<=b_num; i++)
            scanf("%d", &req_time[i]);
        
        // 제한조건 입력받기
        for(int i=1; i<=res_num*2; i+=2)
            scanf("%d %d",&res[i], &res[i+1]);
        
        scanf("%d",&goalnum);
        
        // 소요시간 계산(재귀적)
        result = getMakingTime(goalnum, res_num, req_time, res, maketime);
        
        printf("%d",result);
        
        free(req_time);
        free(res);
        free(maketime);
    }
    return 0;
}

// parent = 소요시간을 구할 빌딩 넘버
// ridx = 제한조건이 오름차순으로 정렬돼있다는 가정 하에 연산시간을 줄이기 위해 현재 어디까지 계산하며 내려왔는지 idx 값 전달
int getMakingTime(int parent,int ridx, int* t_req_time, int* t_res, int* maketime){
    
    // 자식 제한조건들의 소요시간을 각각 저장 (최장거리 선택용
    int time[10]={0};
    int tidx=0;
    
    // 가장 큰 time배열의 idx를 구할 때 쓸 변수
    int midx=0;
    
    //인덱스가 -1이하가 전달됐으면 0을 반환
    if(ridx<0)
        return 0;
    
    // 현재 제한조건 부터 맨처음 제한조건까지 돌면서 자신보다 우선되는 건물을 찾는다
    for(int i=ridx; i>0; i--){
    
        //제한조건이 자신에게 해당된다면
        if(t_res[i*2] == parent){
            
            //만약 제한조건이 구해지지 않았다면
            if(maketime[t_res[i*2-1]] == 0)
                time[tidx++] = t_req_time[parent] + getMakingTime(t_res[i*2-1], i-1, t_req_time, t_res, maketime);
            //이전에 구해서 memoize돼있다면
            else
                time[tidx++] = t_req_time[parent] + maketime[t_res[i*2-1]];
        }
    }
    
    //자신에게 걸려있는 제한조건이 없다면 본 건물의 건설시간만 반환
    if(tidx==0)
        return t_req_time[parent];
    
    //저장된 자식 제한조건들 중 가장 오래 걸리는 시간을 찾아 반환
    for(int i=1; i<tidx; i++){
        if(time[i] > time[midx])
            midx = i;
    }
    return time[midx];
}

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

문제

문제

출처

ICPC

런타임에러 질문입니다..!

skcrabbit 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말