강의로 돌아가기
김재욱

효율성 테스트

효율성 테스트에서 하나밖에 맞추지 못하는데 시간복잡도를 줄여야하는건가요?

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(int K, vector<vector<int>> travel) {
    int answer = 0;
    int arr[2][100001] ={0,};
    //첫번째는 이동한 시간 두번째는 모금액

    arr[0][travel[0][0]]=travel[0][1];
    arr[0][travel[0][2]]=travel[0][3];
    int t=0;
    int min1=min(travel[0][0],travel[0][2]);

    for(int i=1;i<travel.size();i++){
        t++;
        for(int j=travel[i][0];j<=K;j++){
            //cout<<i<<" "<<j<<" "<<j-travel[i][2]<<" "<<j-travel[i][0]<<" "<<arr[i-1][j]<<endl;
            arr[t%2][j] = max((arr[(t+1)%2][j-travel[i][0]]+travel[i][1]), (arr[(t+1)%2][j-travel[i][2]]+travel[i][3]));  


        }
         min1 += min(travel[i][0],travel[i][2]);

    }

    int cmax=0;
    //이동 불가능한 경우 고려해야함 
    for(int i=0;i<=K;i++){
        //cout<< arr[t%2][i]<<endl;;

        if(arr[t%2][i]>cmax)
            cmax = arr[t%2][i];
    }
    if(min1>K){
        //cout<<min1;
        cmax=0;
    }
    return cmax;
}
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.