[BOJ 1402] 아무래도이문제는A번난이도인것같다

1) 문제 링크

https://www.acmicpc.net/problem/1402

2) 접근

$A, B$에 대해 범위 조건만 제시되어 있을 뿐… 정수라는 조건으로는 당최 추론 가능한 성질이 딱히 없었다. 종만북에서 본 대로, 가장 작은 입력에 대해 먼저 생각해 보기로 했다. 일단 $A, A’$ 중 덧셈으로 표현되는 $A’$에 대하여 case를 만들어 내기 편하므로 $A’$를 조작하고 $A$를 고정하기로 했다.

① $A=0$
$A’=A’+0$이므로 가능.

② $A=1$

• $A’>0$인 경우
  $A’=1+1+…+1$(1이 $A’$개)이므로 가능
• $A’=0$인 경우
  $A’=-1-1+1+1$이고, $-1,-1,1,1$ 곱하면 1이므로 가능.
• $A’<0$인 경우
  $A’=-1-1-…-1$(-1이 $-A’$개). $-A’$가 짝수이면 가능. 홀수이어도 $A’=(-A’$개의 $-1)-1+1$로 생각하면 되므로 가능.

③ $A=-1$
$A=1$일 때 만족시키는 조합에서 $-1, +1$을 추가하면 되므로 가능.

이에 따라 $A$가 $-1, 0, 1$이면 임의의 정수 $A’$에 대하여 가능함을 보였다.

이제 $A$의 크기를 키워서, $A$와 $A’$의 관계에 따라 가능 여부를 판별해 보기로 했다. 앞선 추론에서 $A<A’$이면 가능할 것이라는 확신이 들었기 때문에 관계를 이용하기로 한 것이다.

• $A<A’$
  $A’=A+1+1+…+1(1$이 $(A’-A)$개$)$이므로 가능
• $A=A’$
  $A’=A$이므로 가능(문제에서 $a_n$이 단 1개만 존재하는 case)
• $A>A’$
  $A’=A-1-1-…-1(-1$이 $(A-A’)$개$)$이므로 덧셈을 구성하는 수를 모두 곱하면 $A$ 또는 $-A$. 이때 $-A$인 경우 끝에 $-1, 1$을 곱해주면 가능.

결국 임의의 정수 $A, B$에 대하여 $A$는 $B$로 변할 수 있음을 알 수 있었다.

3) 풀이

#include <iostream>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    long long a, b;
    cin >> t;

    for(int i=0; i<t; ++i)
        cin >> a >> b;

    for(int i=0; i<t; ++i)
        cout << "yes" << '\n';
}

4) 피드백

이런 식의 발상을 요구하는 문제를 ‘구성적’인 문제라고 하는 거 같다.
코포 같은 곳에서도 ‘constructive algorithm’으로 태그되어 있는 문제들이 있는데, 아마 이걸 말하는 것 같다.
대체로 귀납적으로 규칙을 유추해서 증명까지 해내도록 유도하는 방식인데, 이런게 창의력 길러주기에 참 좋은 문제라고 생각한다.