Q 17945 통학의 신

💡 문제 요약 및 분석

이차방정식 x^2 + 2Ax + B = 0 풀면 되는 문제. 문제에서 방정식의 근은 항상 정수라는 조건을 주었으므로 답은 인수분해로 얻어낼 수 있다.

💡 알고리즘 설계

첫 번째 계수 X^2 는 1로 고정되므로 이 문제에서는 신경쓰지 않아도 될 것 같다. A,B 값에 따라 계수 a, b가 결정된다. 방정식을 인수분해 하려면 아래 조건을 모두 만족시키는 m, n을 구해야 한다. 두 개 값을 구하고 +- 부호를 반전시키면 이 문제의 정답인 근이 된다.

m + n = a
m * n = b

이렇게 구한 근을 오름차순으로 정렬시켜야 한다. 근은 1개 혹은 2개일 것이기 때문에 복잡한 자료구조는 필요 없고 조건문으로 처리하면 될 것 같다.

💡 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // A,B 입력 받음. A의 경우 문제에서 제시한 방정식이 2A 이므로 2를 곱해준다.
        int a = 2 * sc.nextInt();
        int b = sc.nextInt();

        // 인수분해 실행 (m,n 의 범위는 -b <= m,n <= b 가 될 것이다.)
        int m = 0;
        int n = 0;
        if (b > 0 || b == 0) {
            for (int i = b; i >= -b; i--) {
                int j = a - i;
                if (i * j == b) { // 조건을 만족하는 값이 m,n 이 된다. 여기서 +,- 부호를 반전시키면 문제의 정답인 근이 된다.
                    m = -i;
                    n = -j;
                    break;
                }
            }
        }

        if (b < 0) {
            for (int i = b; i <= -b; i++) {
                int j = a - i;
                if (i * j == b) {
                    m = -i;
                    n = -j;
                    break;
                }
            }
        }

        // 오름차순 정렬
        if (m == n) { // 중근인 경우 한 개만 출력
            System.out.println(m);
        } else if (m < n){
            System.out.println(m + " " + n);
        } else {
            System.out.println(n + " " + m);
        }
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(n)O(1)
  • 단순 반복문이므로 루프 범위 b 의 값에 따라 시간 크기가 선형적으로 증가한다.

  • 사용된 변수들 중에서 배열이나 리스트, 재귀 호출 등은 없이 정수형 변수만 있으므로 공간 복잡도는 O(1) 이다.

💡 틀린 부분 수정

💡 다른 풀이

다른 사람들 풀이를 보니 아예 문제에서 제시한 방정식을 그대로 넣어서 boolean 값을 리턴받는 로직이 눈에 띄었다. 나는 인수분해 자체를 구현하는 것에 집중했는데, 방정식을 그대로 갖다 넣고 for 문으로 x 의 값을 찾으면 훨씬 간단하게 구현할 수 있다는 점을 깨달았다..

public static boolean ikOK(int A, int B, int x) {
    return x * x + 2 * A * x + B == 0;
}

💡 느낀점 및 기억할 정보

‘인수분해’라는 수학공식을 코드로 구현하는 방법에 대해 고민을 많이 했는데 방정식 자체를 넣고 true, false 를 반환하는 방식으로 풀어도 된다는 점이 허무하긴 했다. (듣고 보면 간단한데 깨닫기 어려웠다) 그리고 x 값은 b 보다 크지 않을 것으로 판단하고 범위를 지정한 것은 좋았다고 생각하지만, 그로 인해 조건문이 여러 개 추가되어서 (b가 +인지 -인지 판단해야 하므로) 복잡한 코드가 된 것 같다. 오히려 다른 정답들처럼 단순하게 -1000 <= x <= 1000 으로 지정하는 것이 (어차피 2000개 루프가 그리 큰 사이즈는 아니므로) 가독성 좋은 코드가 되었을 것 같다.