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

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

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

 

혼자 힘으로 풀었는가? O?X?

알고리즘 분류
 - 수학
 - 애드 혹
 - 해 구성하기

문제

어떤 정수 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(-231 ≤ A, B ≤ 231-1)가 주어진다.

출력

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

 

---

 

풀고 나니 쓰레기 같은 문제였다.

 

처음엔 소인수분해를 한 다음 각 수마다 찾아줘야 하는 줄 알았다.

 

물론 난 첫 케이스에 소인수분해를 하진 않았지만 말이다.

 

예시에 나온

 

6 5
6 = 2 * 3
5 = 2 + 3

6 6
6 = 1 * 2 * 3
6 = 1 + 2 + 3

 

위와 같이 표기할 수 있기 때문에

import sys
import math
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())

    for i in range(1, a//2):
        if a % i == 0:
            k = a // i
            if i + k == b or i+k+1 == b:
                print("yes")
                break
    else:
        print("no")

처음엔 위와 같이 풀었다.

 

혹시 풀리나..? 싶었으나 시간초과가 발생하였고

 

여러 시도를 해봤으나 해결되지 않아 

 

백준의 질문게시판을 본 결과

 

a1 a2 ... an이

 

중복되지 않은 값을 가지지 않을 수도 있겠구나 생각되었다.

 

예를 들어

 

1 100
1 = 1 * 1
100 = 1 + 1 + 1+ 1+ 1+ 1+...+ 1
yes

이런 식으로 표기가 가능하다는 것이었다...

 

---

import sys
import math
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    print("yes")
    '''
    for i in range(1, a//2):
        if a % i == 0:
            k = a // i
            if i + k == b or i+k+1 == b:
                print("yes")
                break
    else:
        print("no")
    '''

사실상 그냥

두 수를 입력받고

 

전부 다 yes 출력해 주면 끝인 문제였다.