[백준] 19532번 : 수학은 비대면강의입니다 (브론즈 Ⅱ) - Java/자바

---

✅ 문제

문제링크

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

 

---

✅ 풀이

🔹 코드 1

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] cons = new int[6];
        int x, y;

        for (int i = 0; i < 6; i++) {
            cons[i] =Integer.parseInt(st.nextToken());
        }

        for (int i = -999; i <= 999; i++) {
            for (int j = -999; j <= 999; j++) {
                int equation1 = cons[0] * i + cons[1] * j;
                int equation2 = cons[3] * i + cons[4] * j;
                if (equation1 == cons[2] && equation2 == cons[5]) {
                    x = i;
                    y = j;
                    sb.append(x).append(" ").append(y);
                }
            }
        }
        System.out.println(sb);
    }
}

 

$\begin{cases}\;ax\;+\;by\;=\;c\\\;dx\;+\;ey\;=\;f\end{cases}$

 

다음 연립방정식에서 $x$ 와 $y$ 의 값을 계산하는 문제이다.

$x$ 와 $y$ 가 각각 -999 이상 999 이하의 정수이므로 각각의 값을 하나씩 다 대입해보는 방식을 채택해보았다.

즉, 브루트 포스(Brute Force) 알고리즘을 사용해 보았다.

int형 cons 배열에 계수들을 입력받아 저장하고 이후에 for문을 통해 i가 x, j가 y로 각각 -999부터 999까지 값을 대입해서 맞는 값을 찾는다.

성립하는 x, y를 출력해주도록 한다.

 

🔹 결과 1

 

🔹 코드 2

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(reader.readLine());
        StringBuilder sb = new StringBuilder();
        
        int a = Integer.parseInt(token.nextToken());
        int b = Integer.parseInt(token.nextToken());
        int c = Integer.parseInt(token.nextToken());
        int d = Integer.parseInt(token.nextToken());
        int e = Integer.parseInt(token.nextToken());
        int f = Integer.parseInt(token.nextToken());

        int x = (c * e - b * f) / (a * e - b * d);
        int y = (c * d - a * f) / (b * d - a * e);
        
        sb.append(x).append(" ").append(y);
        System.out.println(sb);
    }
}

 

연립방정식을 수학적으로 계산해서 $x,\;y$ 와의 관계를 찾아보도록 하자.

 

$a·e·x\;+\;b·e·y\;=\;c·e$

$b·d·x\;+\;b·e·y\;=\;b·f$

두 식을 빼보도록 하자.

$(a·e\;-\;b·d)·x\;=\;(c·e\;-\;b·f)$

 

$x\;=\;\cfrac{c·e\;-\;b·f}{a·e\;-\;b·d}$

 

 

$a·d·x\;+\;b·d·y\;=\;c·d$

$a·d·x\;+\;a·e·y\;=\;a·f $

두 식을 빼보도록 하자.

$(b·d\;-\;a·e)·y\;=\;(c·d\;-\;a·f)$

 

$y\;=\;\cfrac{c·d\;-\;a·f}{b·d\;-\;a·e}$

 

다음과 같이 $x,\;y$ 관계를 찾았으니 이를 코드로 구현해보자.

int x = (c * e - b * f) / (a * e - b * d);

int y = (c * d - a * f) / (b * d - a * e);

로 구현하고 x, y를 출력해주도록 한다.

여기서 x, y가 정수이므로 int형으로 선언하면 된다.

이렇게 하면 for문 반복을 하지 않아도 되므로 계산을 줄일 수 있다.

 

🔹 결과 2

 

🔹 알게된 정보

• 수학적 내용을 코드로 작성하는 것에 대해 배우게 되었다.

 

🔹 브루트 포스(Brute Force)

• 브루트 포스(Brute Force)는 문제를 해결하기 위해 가능한 모든 경우의 수를 전부 탐색하는 가장 단순하고 직관적인 알고리즘 기법이다.
• 완전 탐색이라고도 한다.
• 가능한 모든 경우를 하나하나 시도해보는 방식이다.
• 정답을 보장하지만, 시간이 오래 걸릴 수 있다.
• 구현이 간단하고 최적화보다는 정답성에 초점을 맞춘다.
• 시간 복잡도가 매우 크므로 (보통 $O(n!)$, $O(2^{n})$, $O(n^{2})$ 등) 입력 크기가 조금만 현실적으로 실행 불가능해진다.
• 가능한 경우의 수가 작고 더 나은 알고리즘이 복잡하거나 떠오르지 않을 때 사용한다.

 

---