[HackerRank/C++] Manasa and Stones

숫자 a, b가 각각 적힌 두개의 돌이 있다

 

n번만큼 a,b 값 둘중 하나만큼 이동했을때, 해당 위치에는 보물이 숨겨져 있다고 한다

 

보물이 숨겨져 있을 가능성이 있는 모든 위치를 오름차순으로 정렬해 return 한다

vector<int> stones(int n, int a, int b)
{
    vector<int> result;
    result.reserve(n);
    
    if (a == b)
    {
        result.push_back(a * (n - 1));
        return result;
    }
    else if (a > b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    
    for (int i = 0; i < n; ++i)
    {
        result.push_back(a * (n - i - 1) + b * i);
    }
    
    return result;
}

모든 경우의 수를 따질 것 없는 문제다

 

a + b + a + a나 a + a + a + b나 값에는 차이가 전혀 없기 때문이다

 

결국 같은 값을 제외한 모든 경우의 수는 n개만큼이므로 result를 n만큼 미리 reserve 해둔다

 

첫번째로 만약 a와 b가 같다면 나올 값은 0은 결과값에 포함하지 않으니 a * (n - 1)이 되며, 그대로 return 한다

 

두번째로 a와 b의 크기를 비교해 어느 값이 더 큰지 찾아내 a를 작은 값으로 두겠다

 

이후 오름차순으로 배열을 반환해야 하므로 a * (n - 1 - i)와 b * i를 더해준 값을 n번만큼 돌며 result에 push_back하고 return 한다