문제파악과 영어능력은 중요하다

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

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

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

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

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

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

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

많이 풀어보도록 하자.

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

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

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

#include <math.h>
 
int solution(vector<int> &A) {
    if (A.size() == 0) return 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;
}