단순하게 최소 공배수를 구하는 문제이다.

이 문제에서 포인트는 최소 공배수는 A와 B 가 주어졌을 때  "A*B / 최대공약수" 를 계산해 구할 수 있다. 는 것이다.

결국 유클리드 호제법을 이용해서 최대 공약수를 구하면 해결 할 수 있다. 

유클리드 호제법에 관해 정리해 둔 글이다.

코드는 다음과 같다.

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

public class p1934 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int result = A * B / gcd(A, B);
            System.out.println(result);
        }

    }
    private static int gcd(int A, int B ){
        if(B==0) return A;
        else return gcd(B, A % B);
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12977 

문제를 단순하게 정리하자면, 주어진 문제는 배열에 있는 숫자들 중에 3개를 골라 더했을때 소수가 되는 경우의 개수를 구하면 되는 문제이다. 

처음에 딱 보고 든 생각은 다음과 같다. 

3개의 수는 어떻게 뽑을 것인가..?

방법 1. ) 사실 단순한 방법은 for문을 3번 돌리면서 값을 구한뒤 , 그 값이 소수인지를 판별하는 것이다. 

방법 2. ) 배열의 조합 값들을 모두 찾아내서 정리한뒤 ( 재귀나 백트래킹 이용 ) 조합의 합이 소수인지를 판별하는 것이다.

그래서 일단 두가지 방법을 모두 구현해보고자 했다.

방법 1. - for문을 3번 돌리면서 값을 구하고 그 값을 소수 판별하기

class Solution {
   public int solution(int[] nums) {
        int answer = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int target = nums[i] + nums[j] + nums[k];
                    if(isPrime(target)) answer++;
                }

            }
        }
        return answer;
    }
    private boolean isPrime(int target) {
        for (int i = 2; i <= Math.sqrt(target); i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
    }
}

코드만 봐도 그렇게 어렵지 않다. 

방법 2. 백트래킹을 이용해서 만들수 있는 조합 리스트를 만든뒤, 해당 조합의 합이 소수를 만족하는지 판별하기

import java.util.ArrayList;

class Solution {
      static ArrayList<Integer> list;
    public int solution(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        list = new ArrayList<>();
        comb(nums, visited, 0, nums.length, 3 );
        return list.size();
    }
    void comb(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }
        for (int i = start; i < n; i++ ) {
            visited[i] = true;
            comb(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    void print(int[] arr, boolean[] visited, int n) {
        int target =0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                target += arr[i];
            }

        }
        if (isPrime(target)) {
            list.add(target);
        }
    }
    private boolean isPrime(int target) {
        for (int i = 2; i <= Math.sqrt(target); i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
    }

}