글 읽기 - 도와주세요... 메모제이션 이용했는데 시간초과나와요

krong6930 2년 전 0

함수만 올릴게요. 시간초과가 왜 나나요?

//함수: 아래까지 갔을때 max 반환
//기저사례: 더 이상 갈 곳이 없는 경우 값 자체 반환-> 함수에 넣어줘야함
//0: 0, 1    1: 1, 2   2: 2, 3    3: 3, 4
//current는 row와 col 인덱스

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int wayRemember[501][501];
    init_wayRemember(wayRemember, 501);
    
    vector<int> current;
    current.push_back(0);
    current.push_back(0);
    
    answer = maxWay(triangle, current, triangle.size(), wayRemember);

    return answer;
}

int maxWay(vector<vector<int>>& triangle, vector<int> current, int size, int wayRemember[][501])
{
    int row=current[0], col=current[1];
    if(row==size-1) return triangle[row][col];
    if(wayRemember[row][col]!=-1) return wayRemember[row][col];
    
    
    vector<int> nextFirst, nextSecond;
    nextFirst.push_back(row+1); nextFirst.push_back(col);
    nextSecond.push_back(row+1); nextSecond.push_back(col+1);
    
    wayRemember[row][col]=max(maxWay(triangle, nextFirst, size, wayRemember),
                              maxWay(triangle, nextSecond, size, wayRemember)) 
                            +triangle[row][col];
    
    return wayRemember[row][col];
}

void init_wayRemember(int wayRemember[][501], int size)
{
    for(int i=0; i<501; ++i)
        for(int j=0; j<size; ++j)
            wayRemember[i][j]=-1;
}

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

문제

문제

출처

ICPC

도와주세요... 메모제이션 이용했는데 시간초과나와요

krong6930 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말