생각 유도

처음에 easy를 풀었을 때, n <= 5000 까지여서, 브루트 포스로 접근해야 겠다고 생각이 들었고, n^2 의 알고리즘으로 바로 풀렸다.
하지만 hard 같은 경우는 n<= 2n^6 이다. 이는 최적화를 시켜야 하고, 최적화를 시키는 방법중에서 나누어 떨어지는 수는 ii<=n 를 넘지 않으므로 이는 바로 떠올릴 수 있었다.
하지만 for 문을 두번 도므로 i*i<= n을 다 검사하면 이중포문에서 시간 초과가 난다. 따라서 factor 배열에 미리 담아 준 후 이중 포문을 돈다.

방법

해결 방법

1. factor 가 되는 숫자들을 각각 담아준다

• a * c = n (factor 1 ArrayList)
• b * d= -(n + 2) ( factor 2 ArrayList)

2. check를 한다. ( a d + b c = n+1)

생각해야 할 것

브루트 포스를 어떻게 최적화 시킬 것인가. 에 대해서 생각하자. 나누어 떨어지는 수는 다음과 같이 소인수 분해 배열을 미리 생성시키므로써 최적화 가능하다.

코드

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

public class Main {
    /*
    * Acx^2 + (ad +bc) + bd = nx^2 + (n+1) x - (n+2)
Ac = n;
ad+ bc = n+1;
Bd = - (n+2) ;
    * */
    public static StringTokenizer st = null;

    public static BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));

    public static int n;
    public static StringBuilder sb = new StringBuilder();

    public static boolean checkACBD(int a, int b) {
        int c = n / a;
        int d = -(n + 2) / b;
        if (a * d + b * c == n + 1) {
            sb.append(a).append(" ").append(b).append(" ").append(" ").append(c).append(" ").append(d).append("\n");
            return true;
        }
        return false;
    }


    public static ArrayList<Integer> factor = new ArrayList<>();
    public static ArrayList<Integer> factor2 = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        // 1. ac 정하기
        // 2. bc 정하기
        boolean flag = false;
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                factor.add(i);
                factor.add(n / i);
            }
        }
        for (int i = 1; i * i <= n + 2; i++) {
            if ((n + 2) % i == 0) {
                factor2.add(i);
                factor2.add((n + 2) / i);
            }
        }

        loop:
        for (int i = 0; i < factor.size(); i++) {
            int a = factor.get(i);
            for (int j = 0; j < factor2.size(); j++) {
                int b = factor2.get(j);
                if (checkACBD(a, b)) {
                    flag = true;
                    break loop;
                }
            }
        }
        if (flag) System.out.println(sb);
        else System.out.println(-1);
    }
}

결과