Codility에서  Dynamic Programming 문제를 푸는 도중,

set 이라는 것을 무심코 넘겼다가 피 보는 일이 생겼다.

set {-1, 1} 이면 한 집합이고, 이 안에 들어 있는 원소를 임의로 사용할 수 있는 것인데,

나는 이 집합이 배열의 일부이고, {-1. 1}이 반복되는 배열이라 내가 건드릴 수 없는 영역이라 판단했다.


또한 식을 살펴보면 배열의 모든 원소를 더하는 소스인데도 일부만 더할 수 있다고 마음대로 판단해 버렸다.

문제가 무엇인지 제대로 파악하는 능력, 모의고사같은 실력을 평가하는 영어 실력 뿐만이 아닌 실용적인 영어 실력(set=집합 등)을

기를 필요성이 있어 보인다.


많이 풀어보도록 하자.

일단 짠 소스는 아까우니까 올려두도록 하겠다.


임의의 길이의 vector<int> A가 주어질 때, 이 배열에 {-1. 1. -1, 1...} 을 곱하고,

부분합의 절댓값의 최소값을 구하는 소스는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <math.h>
 
int solution(vector<int> &A) {
    if (A.size() == 0return 0;
    vector<int> psum;
    psum.push_back(0);
    int sum = 0;
    for (int i = 0; i<A.size(); i++) {
        sum += A[i] * ((i % 2) ? -1 : 1);
        psum.push_back(sum);
    }
 
    int minSum = abs(psum[1]);
    for (int i = 2; i <= A.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (minSum > abs(psum[i] - psum[j])) minSum = abs(psum[i] - psum[j]);
        }
    }
    return minSum;
}
cs


'잡담' 카테고리의 다른 글

ESTSOFT 코딩테스트 합격  (1) 2016.06.29
ESTSOFT 코딩테스트 후기  (19) 2016.06.27
Todo List  (0) 2016.06.24
갈수록 시간복잡도가 중요해지네  (0) 2016.06.18
학교 다니면서 다 한다는게 힘들긴 하구나  (0) 2016.06.17
블로그 이미지

__미니__

E-mail : skyclad0x7b7@gmail.com 나와 계약해서 슈퍼 하-카가 되어 주지 않을래?

,