[SWEA] 17642 최대 조작 횟수 (Java)

1.  문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYj_Dz-6qLgDFASl#none

2.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();
    
    static long a0;
    static long b0;
    
    static void input() {
        a0 = scanner.nextLong();
        b0 = scanner.nextLong();
    }
    
    static void solution() {
       	long diff = b0 - a0;
        if(diff < 0 || diff == 1) {
            answer.append(-1).append('\n');
            return;
        }
        
        if(diff % 2 == 0) {
            answer.append(diff / 2).append('\n');
            return;
        }
        
        long primeNumberCount = 1;
        diff -= 3;
        primeNumberCount += diff / 2;
        answer.append(primeNumberCount).append('\n');
    }
    
	public static void main(String args[]) {
        int T = scanner.nextInt();
        for(int test = 1; test <= T; test++) {
         	answer.append('#').append(test).append(' ');
            input();
            solution();
        }
        
        System.out.print(answer);
	}
    
    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
         	while (st == null || !st.hasMoreElements()) {
             	try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                 	e.printStackTrace();   
                }
            }
            
            return st.nextToken();
        }
        
        int nextInt() {
         	return Integer.parseInt(next());   
        }
        
        long nextLong() {
         	return Long.parseLong(next());   
        }
    }
}

3.  접근

• A에는 임의의 소수를 더하고, B에는 임의의 소수를 빼서 A와 B를 같게 만들어야 한다.
  • 즉, A가 B보다 크다면 두 수를 같게 만들 수 없다.
  • 또한 소수 중 가장 작은 값이 2이기 때문에 A와 B 사이의 차이가 1 밖에 나지 않는다면 두 수를 같게 만들 수 없다.
  • 이러한 경우에는 -1을 출력한다.
• A와 B를 같은 수로 만들 때 최대 횟수로 연산을 진행하여야 한다. 즉, A에 임의의 소수를 더하거나 B에 임의의 소수를 빼는 횟수가 최대 횟수가 되어야 한다.
  • 연산의 횟수를 늘리기 위해서는 작은 수를 이용하여야 한다.
  • 그러므로 2, 3만을 이용하여 연산을 진행한다.
    • A와 B의 차이에 해당하는 수를 2, 3으로 만들 수 있다면 2, 3만을 이용하여 A와 B를 같은 수로 만들 수 있다.
    • 2 이상의 수는 2, 3만을 이용하여 만들 수 있기 때문에 2, 3만을 이용하여 연산을 진행해도 문제 없다.
  • 만약 차이가 짝수라면 2만을 이용하여 연산을 진행하고, 차이가 홀수라면 2만을 이용하여 해당 수를 만들 수 없으니 3을 한 번 이용하여 짝수를 만들고, 나머지 수를 2를 이용하여 연산을 진행한다.