백준 1402번 아무래도 이 문제는 A번 난이도인 것 같다 - C++

문제

---

어떤 정수 A가 있으면 그 숫자를 A = a1 * a2 * a3 * a4 ... * an으로 했을 때 A' = a1 + a2 + a3 ... + an이 성립하면 "A는 A'으로 변할 수 있다"라고 한다. (ai는 정수) 만약 A'이 A''으로 변할 수 있으면 "A는 A''으로 변할 수 있다"라고 한다.

이때 A와 B가 주어지면 A는 B로 변할 수 있는지 판별하시오.

 

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)이 주어진다. 테스트 케이스마다 두 정수 A, B(-2^31 ≤ A, B ≤ 2^31-1)가 주어진다.

 

출력

각각의 테스트 케이스마다 한 줄에 변할 수 있으면 yes, 아니면 no를 출력한다.

 

문제 링크

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

 

 

풀이

---

 처음에는 정말 아무 생각없이 소인수분해를 다 해서 벡터에 값을 넣고, 그걸 다 더하는 식으로 풀었다. 근데 시간 초과가 나길래 생각을 조금 해보니, int 최대, 최소값 모두 들어올 수 있어서 자칫 잘못하면 순회를 억을 넘는 횟수를 할 수 있었다.

 

그러나 진짜 문제는 이게 아니다. 뭘 하든 답은 "yes"라는 것이다.

 

문제에서 A를 an의 곱으로 나타낸다고 할 때, an은 소수라는 말이 없다. 그말은 -1과 1도 곱해도 상관 없다는 것이다.

 

"엥 근데 A가 0, B도 0같은 인풋은 말이 안되는거 아닌가요?"

 

...라고 할 수 있다.

 

근데 이것도 가능하다. $A = -1 * -1 * -1 * -1 * -1 * -1 * 0$ 이면 $A$가 $0$, $B$가 $0$도 된다. 결국 결론은 $-1$과 $1$의 곱으로 표현하면서 어떻게든 $B$의 값에 맞출 수 있다는 것이다.

 

프로그램 동작

위의 풀이대로 접근하면 어떤 인풋이 와도 전부 다 가능하므로 "yes"만 출력하면 된다.

 

 

C++ 코드

---

#include <iostream>

using namespace std;

int main() {
    int T, A, B, tmp;

    cin >> T;
    while (T--) {
        cin >> A >> B;
        cout << "yes\n";
    }
}