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개 루프가 그리 큰 사이즈는 아니므로) 가독성 좋은 코드가 되었을 것 같다.