[ lesson 03_3 ] TapeEquilibrium

code

#include<cstdlib>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int minimal = 999999999;
  
    
    for(int p = 1; p<A.size(); p++){
          int sum_front = 0;
          int sum_back = 0;
        for(int i=p-1; i>=0; i--){
            sum_front += A[i];
        }
        
        for(int j=p; j<A.size(); j++){
            sum_back += A[j];
        }
        
        minimal = min(minimal, abs(sum_front-sum_back));
        
    }
    return minimal;
}

 

result

Time Out Error다.. Killed는 너무 했잖아..(｡•́-ก̀｡)

 

<해결 아이디어>

p-1 ~ 0까지 합인 sum_front

p ~ A.size()까지의 합인 sum_back의 차를 구한다.

 

이때 int의 절대값을 구하는 abs( , )는 <cstdlib>를 추가해줘야한다.

 

그리고 minimal에 999 999 999를 넣었는데

이는 100,000개가 있고 50,000개가 1000, 50,000개가 -1000일 때 최고 차이가 2000 * 50,000 = 100,000,000가 된다.

따라서 넉넉하게 제일 큰 수를 999,999,999로 설정했다.

 

* sum_front, sum_back 초기화를 p가있는 for문 안에 안 넣어줘서 에러가 떴는데 수정했다.

* 반복문인 for문을 너무 많이 써서 timeout이 된 것 같다. 해결책을 찾아봐야겠다.