[Python, 파이썬] SWEA 17642. 최대 조작 횟수

두 개의 정수 변수 A와 B가 있을 때, 값을 같게 하기 위해 가능한 많은 횟수가 얼만지 구하는 문제.

 

- A 에 임의의 소수(prime number)를 더한다.

- B 에서 임의의 소수(prime number)를 뺀다.

 

두 변수에는 가할 수 있는 연산은 각각 이렇다.

A는 임의의 소수를 더할 수밖에 없고, B는 뺄 수밖에 없다.

 

최대 몇 번을 조작하면 두 변수의 값을 같게 할 수 있을까?

 

 

T = int(input()) # 테스트 케이스의 수 T

for test_case in range(1, T+1):

    A, B = map(int, input().split()) # 변수 A, B
    answer = -1 # 가능하지 않을 시 -1
    
    if(B-A) > 1: # 두 변수의 차가 2 이상일 때
        answer = (B-A)//2 # 최대 횟수

    elif(B-A) == 0: # 값이 같을때는
        answer = 0 # 0
        
    print("#%d %d" %(test_case, answer))

 

 

[문제풀이]

---

 

이 문제 망했는데 왜냐면 너무 어렵게 생각해서다....

처음엔 소수를 빼니까 에라스토스테네스의 체로 B-A의 소수를 구해 DFS를 사용했는데, Runtime Error가 떠서 당황함....

 

곰곰히 생각해보니 사용한 소수를 다시 사용하지 말라는 조건이 없었다.

그럼 하나의 소수를 무한정 사용할 수 있단건데, 그럼 '최대한 많은 수의 횟수를 조작' 하려면 가장 작은 수를 빼는 걸로 쉽게 구할 수 있다.

2 3 5 7 11 13 17 19 ...

 

소수는 이렇게 되있는데 A와 B의 차가 1 이상이기만 하면 2, 그리고 3으로 연산해서 어떤 수든 구할 수 있다.

즉, B-A의 2의 몫을 구하면 최대 조작 횟수다!

0 1
-1 0

 

근데 여기서 주의해야 할 점은 A와 B의 값이 같을 수도 있고, A가 B보다 작을 수도 있단 거다.

또, B-A가 1일 때도 소수를 빼서 조작할 수 없는 건 마찬가지다.

 

그래서 이 경우를 if로 조건 처리해주면 정답이 된다.