문제 링크

분류

수학(Mathematics), 애드 혹(Ad-hoc), 해 구성하기(Constructive)

풀이

1과 -1을 이용한 연산의 특징을 이용하면 문제를 풀 수 있다.

먼저 모든 자연수 $N$은 $N+1$로 변환할 수 있음을 보여보자. $N = 1 * N \Rightarrow N^\prime = 1 + N$이므로 모든 자연수 $N$에 대하여 $N$보다 큰 자연수로 변환할 수 있다.

또한 모든 자연수 $N$은 $N-1$로 변환할 수 있음을 보여보자 $N = 1 * (-1) * (-1) * N \Rightarrow N^\prime = 1 - 1 - 1 + N = N - 1$이므로 모든 자연수 $N$에 대하여 $N$보다 작은 자연수로 변환할 수 있다.

따라서 다음이 성립한다. 그러므로 모든 입력을 받고, 테스트케이스의 개수만큼 “yes”를 출력하면 된다.

\[\forall a, b \in \mathbb{N}, ~ a \Rightarrow b\]

개인적인 감상

처음에는 문제에서의 예시가 $6=2*3 \Rightarrow 5 = 2 + 3$ 이런 형태로 나와있어서 소수와 관련된 문제로 오해하였다. 하지만 애드혹 문제인 만큼 무엇인가 조건에서의 특이한 것을 찾으려고 하니 위와 같은 형태의 식을 얻을 수 있었다. 다음에 애드혹 문제를 풀 때에도 창의적인 생각을 할 수 있도록 노력해야겠다.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n, tmp;
    cin >> n;
    for (ll i = 0; i < 2 * n; i++) {
        cin >> tmp;
    }

    for (ll i = 0; i < n; i++) {
        cout << "yes\n";
    }
}