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

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

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

---

 

22/09/16

 

 

이 문제는 풀고 나서 정말 감탄했던 문제이다. 아이디어가 기가 막히는 문제이다.

---

 

문제 접근 방식:

 

 

문제는 굉장히 짧고 간단하다.

 

어떤 정수 $A$가 있으면 그 숫자를 $A = a_1 * a_2 * a_3 * \cdots * a_n$으로 했을 때 $A' = a_1 + a_2 + a_3 + \cdots + a_n$이 성립하면 "$A$는 $A'$으로 변할 수 있다"라고 한다. ($a_i$는 정수) 만약 $A'$이 $A''$으로 변할 수 있으면 "$A$는 $A''$으로 변할 수 있다"라고 한다.
이때 $A$와 $B$가 주어지면 $A$는 $B$로 변할 수 있는지 판별하시오.

 

위의 지문이 문제의 전부인데, 결론만 이야기하자면 어떤 $A$와 $B$가 주어지든지 간에 항상 변할 수 있다.

 

증명은 다음과 같다.

 

만약 $A < B$라면, $A = A*1$이기 때문에 $A$는 $A+1$로 변할 수 있고, 마찬가지로 $A+1$은 $A+2$로 변할 수 있기 때문에, 수학적 귀납법에 의해 $A$는 $B$로 변할 수 있다.

 

만약 $A > B$라면, $A = -A*(-1)$이기 때문에 $A$는 $-A-1$로 변할 수 있고, $-A-1$은 $-A$로 변할 수 있다. 수학적 귀납법에 의해서, $B$까지 도달 가능하고, 이는 곧 $A$는 $B$로 변할 수 있다는 뜻이다.

 

$A = B$라면 당연히 변할 수 있다.($A = A*(-1)*(-1)*1*1 \rightarrow A + (-1) + (-1) + 1 + 1 = A$)

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1402번 아무래도이문제는A번난이도인것같다
# 수학
'''
접근 방법:
A와 A + 1이 있을 때, 항상 A는 A+1로 변할 수 있음
A+1은 -(A+1)*-1로 해서 -A-2로 변할 수 있으며,
연속해서 A까지 도달 가능
따라서 A가 어떤 숫자든지 간에 항상 변할수 있다.
'''
for _ in range(int(input())):
    print('yes')