Codeforces #1401A Distance and Axis

문제

https://codeforces.com/problemset/problem/1401/A

걸린 시간

01 : 49 : 23

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
typedef long long ll;
using namespace std;

int a, k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> a >> k;
        if(a <= k)
            cout << k-a << "\n";
        else
            if((a+k)%2 == 0)
                cout << 0 << "\n";
            else
                cout << 1 << "\n";
    }
    return 0;
}

constructive algorithms, 구성적 알고리즘 문제. 사고력을 요구하는 문제라고 한다.

중심선 위에 점 o(시작점), a가 있다. o부터 b까지의 거리 - b부터 a까지의 거리 의 절대값이 k가 되도록 하는 점 b가 존재하게끔 a의 위치를 이동시키려고 한다. 한번에 1씩 증가 혹은 감소시킬 수 있다고 할 때 이동횟수의 최소값을 묻고 있다.

한참을 손으로 예제를 풀다보니 답이 나오는 경우를 세가지로 나눌 수 있었다.

1. a가 k보다 작거나 같은 경우
2. a가 k보다 큰 경우
   2-1. a+k 값이 짝수인 경우
   2-2. a+k 값이 홀수인 경우

a가 k보다 작거나 같은 경우는 a가 최소 k이상이어야 조건을 만족시킬 수 있으므로 k-a 만큼 이동시킨다. 이때 b가 a와 같은 위치라고 가정하면 o에서 b까지의 거리는 k, b에서 a까지의 거리는 0으로 더이상 이동할 필요가 없이 k-a 가 정답이 된다.

a가 k보다 큰 경우는 두가지로 나뉘는데 a+k 값이 짝수일 경우는 k값을 만족시킬 수 있는 b의 위치가 o와 a사이에 존재해 이동횟수가 0인 반면, 홀수일 경우는 k값을 만족시킬 수 있는 b의 위치가 존재하지 않았다. 따라서 1을 증가 혹은 감소시켜 짝수로 만들어야하므로 이동횟수는 1이 된다.

같은 유형의 문제로 Baekjoon 19590번 비드맨 이 있다.