[BOJ 19532] 수학은 비대면강의입니다 - [수학, 브루트포스]

[BOJ 19532] 수학은 비대면강의입니다 - [수학, 브루트포스]

문제 링크

https://www.acmicpc.net/problem/19532

문제 요약

주어진 연립방정식 $ax + by = c$, $dx + ey = f$를 만족하는 정수 $(x, y)$쌍을 구하는 문제입니다. $x$와 $y$는 각각 $-999$ 이상 $999$ 이하의 정수임이 보장됩니다.

접근 방법

• 자료구조: 정수형 변수 (int)
• 알고리즘: 브루트포스 (완전 탐색)
• 핵심 아이디어: - $x$와 $y$의 범위가 각각 1,999개로 매우 작습니다.
  • 가능한 모든 $x, y$ 조합($약 2000 \times 2000 = 4,000,000$)을 대입하여 두 식을 모두 만족하는 경우를 찾습니다.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b, c, d, e, f;
    // 계수 입력
    if (!(cin >> a >> b >> c >> d >> e >> f)) return 0;

    // x와 y의 가능한 범위를 모두 탐색 (브루트포스)
    for (int x = -999; x <= 999; x++) {
        for (int y = -999; y <= 999; y++) {
            // 연립방정식의 두 조건을 만족하는지 확인
            if ((a * x + b * y == c) && (d * x + e * y == f)) {
                // 유일한 해가 보장되므로 찾으면 바로 출력 후 종료
                cout << x << " " << y << "\n";
                return 0;
            }
        }
    }

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N^2)$ (여기서 $N$은 정수 범위의 크기인 2,000. 약 400만 번의 연산으로 1초 내에 넉넉히 수행 가능)
• 공간 복잡도: $O(1)$ (상수 개의 변수만 사용)

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms (또는 탐색 위치에 따라 최대 40ms 이내)

핵심 포인트

1. 제한 사항 활용: 문제에서 변수의 범위가 명확히 주어졌을 때, 복잡한 공식(크래머 공식 등)보다 구현이 간단한 완전 탐색이 유리할 수 있습니다.
2. 정수 연산: 모든 연산이 정수 범위 내에서 이루어지므로 부동 소수점 오차 걱정 없이 정확한 비교가 가능합니다.
3. 조기 종료: 문제에서 유일한 해를 보장했으므로 return 0을 통해 불필요한 탐색을 방지합니다.

예제 확인

• 예제 1: 1 3 -1 4 1 7 입력 시 $1(2) + 3(-1) = -1$ 이고 $4(2) + 1(-1) = 7$ 이므로 2 -1 출력 확인.
• 예제 2: 2 5 8 3 -4 -11 입력 시 $2(-1) + 5(2) = 8$ 이고 $3(-1) - 4(2) = -11$ 이므로 -1 2 출력 확인.