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

문제 링크:

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

코드:

#include <stdio.h>

int main(void){
    int a = 0;
    int b = 0;
    int c = 0;
    scanf("%d", &a);
    for(int i = 0; i < a; i++){
        scanf("%d %d", &b, &c);
        printf("yes\n");
    }
    
    return 0;
}

풀이:

입력으로 A와 B가 주어지면 A와 B가 문제의 조건을 만족하는지 판별하는 문제이다. 그런데 정답 코드를 보면 no출력 부분이 없다. 왜일까? yes만 출력하는 코드이기 때문이다. 다시 말하면 A와 B가 어떤 정수던 간에 조건을 무조건 만족한다는 뜻이다. 그럼 그 이유는 무엇일까?
문제에서는 A가 a1*a2*a3 ...으로 표현될 때 B가 b1+b2+b3 ...으로 표현될 수 있는지 판별하라고 했다. A=6, B=4라고 가정할 때 A는 1*6, 2*3등으로 표현될 수 있다. 그러므로 B는 1+6, 2+3으로 표현되어야 해서 조건을 만족하지 못한다고 생각할 수 있지만, 표현할 수 있는 가짓수가 훨씬 많다.
모든 수는 1을 곱하면 그대로고, -1을 두 번 곱해도 그대로이다. 그러니까 A는 1*6*1, 2*3*(-1)*(-1)등으로 표현할 수 있다. 이제 A의 표현을 조건에 만족하도록 바꾸어 보면 2*3*1*(-1)*(-1)로 바꿀 수 있다. 그러면 B는 4=2+3+1-1-1로 표현할 수 있기에 문제의 조건을 만족한다. 이는 A와 B에 어떤 정수를 대입하더라도 모두 성립한다.