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

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

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

#include <stdio.h>
#pragma warning(disable:4996)
int main() {
	int r, n, n1;
	scanf("%d", &r);
	for (int i = 0; i < r; i++) {
		scanf("%d %d", &n, &n1);
		printf("yes\n");
	}
	return 0;
}

이 문제는 참 할 말이 많다...

 

힌트

6 = 2*3, 2+3=5이므로 성립한다.

힌트가 이런 식으로 주어져 있어서 처음에는 인수분해를 이용해서 문제를 풀어야 하나 생각했다.

하지만 내 머리로는 생각도 불가능하고 길이를 생각해봐도 출력이 초과될 것 같았다.

막상 답을 구했을 때는 참... 이거 풀겠다고 1시간을 썼나 싶을 정도로 간단한 답이 도출되었다.

답은 항상 yes이다...

왜 그럴까? 보기에는 항상 yes인 것은 불가능해 보인다. 

하지만 이 점을 생각해보아야 한다.

a 가 b가 되기 위해서 곱할 수 있는 i는 제한이 없다.

음... 그래도 이해가 쉽지 않을 수 있다, 그러니 예시를 하나 들어보자.

a는 4를 입력받았고, b는 10을 입력받았다.

4 = 2 * 2, 10 = 2 + 8

엥 ? 어림도 없는 결과가 나온다.

하지만 이렇게 생각해보자. 

4는 4 * 1 *1 *1 *1 *1 *1 *1 *1 *1 *1 *1 *1 *1 *1 *1...... 와 같이도 나타낼 수 있다.

그럼 다시 a와 b를 보자

4 = 4 * 1 * 1 * 1 * 1 * 1 * 1, 10 = 4 + 1 + 1 + 1 + 1 + 1 + 1

이렇게도 성립한다.

허 참... 항상 논리적으로 생각할 필요가 있는 것 같다.