8458

static int N;
static int x, y;
 
static int solution(void)
{
    queue<int> q[2];
    int max = 0, sum = 0, cond = 0;
    int ret;
 
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &x, &y);
        if (x < 0)
            x = -x;
        if (y < 0)
            y = -y;
 
        sum = x + y;
        q[sum % 2].push(sum);
 
        if (sum > max)
            max = sum;
    }
 
    if (q[0].size() && q[1].size())
        return -1;
 
    if (q[1].size())
        cond = 1;
 
    sum = 0;
    for (ret = 0; ; ret++)
    {
        sum += ret;
        if (sum >= max && sum % 2 == cond)
            break;
    }
         
    return ret;
}

일단 문제 풀이 조건 중 가장 중요한 힌트가 읽기에 따라 오해의 소지가 있는 듯 하다.

"i번째 움직임에서 각 점은 상하좌우로 i만큼의 거리를 반드시 이동해야 한다."

위 문장을 나는 아래와 같이 이해하였다,

상하좌우 중 한방향으로만 i만큼 이동해야한다.

 

그러나 이렇게 이해해야 문제를 풀 수 있다.

상하좌우 모두 포함해서 i만큼 이동해야 한다.

즉, (0, 0) 상태에서 i가 6인 경우 ↑↓↑↓↑↓ 이렇게 해서 (0, 0)을 유지할 수 있는 것이다.

 

또, x, y 좌표 각각이 중요해지지 않고, 전체 얼마만큼 이동해야 하는지가 중요해진다.

(-3, 1) 인 경우 총 4의 이동이 필요하다.

 

i = 1, 2 로 총 3의 이동을 만들어 낼 수 있다.

그러나 1이 모자라 i = 3 일 때 모자란 1을 채워 (0, 0)으로 옮길 수 있고, 나머지 2는 제자리 이동을 시키면 된다.

 

(2, 3) 인 경우 총 5의 이동이 필요하다.

i = 1, 2, 3 으로 총 6의 이동을 만들어낸다, 그러나 1이 남아서 (0, 0)은 안된다. 이를 편의상 (0, 1)로 하겠다.

다음 i = 4 이다. 역시 (0, 0)으로 옮길 수 없다. 그래서 편의상 (2, 3)로 이동 시키겠다.

다음 i = 5 로 (0, 0)으로 이동 시킬 수 있다.

 

여기서 중요한 점은 i 가 리니어 하게 증가하는데 그 합이 전체 이동 거리 이상이면서, 짝수면 짝수, 홀수면 홀수 여야 한다는 것이다.

 

또, 실패의 조건은 각 좌표들의 절대 값의 합 중에 다른 성질의 수가 없다면 전체 좌표를 (0, 0)으로 이동 시킬 수 없다는 것이다.