문제
자세한 문제 내용은 ‘수학은 비대면강의입니다‘를 클릭하세요.
풀이
이 문제는 브루트 포스 알고리즘을 이용하거나, 2차 방정식의 특성을 이용하여 풀 수 있습니다.
브루트 포스 알고리즘을 사용한다면, x와 y 값이 -999에서 999까지의 범위로 주어졌으므로, 모든 경우를 탐색하며 대입한 값을 확인해봅니다.
|
1 2 3 4 5 6 7 |
for (x in -999..999) { for (y in -999..999) { if (a * x + b * y == c && d * x + e * y == f) { return "$x $y" } } } |
연립방정식을 사용한다면 다음의 풀이 과정을 거칩니다.
주어진 연립방정식은 다음과 같습니다.
가감법을 사용하여 이 연립방정식을 풀기 위해서는 먼저 한 변수를 제거해야 합니다. 이를 위해 두 방정식을 적절히 곱하여 두 방정식의 x 또는 y의 계수를 동일하게 만들 수 있습니다.
예를 들어, x의 계수를 동일하게 만들기 위해 첫 번째 방정식에 d를 곱하고, 두 번째 방정식에 a를 곱합니다.
이제 두 방정식을 빼면 x 항이 사라집니다:
이를 y에 대해 정리하면, 아래와 같은 식으로 정리됩니다.
x 또한 동일한 과정을 통해 식을 정리합니다.
|
1 2 |
val x = (c * e - b * f) / (a * e - b * d) val y = (c * d - a * f) / (b * d - a * e) |
테스트 코드
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import io.kotest.core.spec.style.StringSpec import io.kotest.matchers.shouldBe import java.io.BufferedReader class No19532Test : StringSpec({ "수학은 비대면강의입니다 : https://www.acmicpc.net/problem/19532" { val testCases = listOf( "1 3 -1 4 1 7" to "2 -1", "2 5 8 3 -4 -11" to "-1 2" ) testCases.forEach { (given, expected) -> val actual = No19532.solve(BufferedReader(given.reader())) actual shouldBe expected } } }) |
프로덕션 코드
브루트 포스 알고리즘 사용
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.io.BufferedReader fun main() { val input = System.`in`.bufferedReader() val output = System.out.bufferedWriter() output.write(No19532.solve(input)) input.close() output.flush() output.close() } object No19532 { fun solve(input: BufferedReader): String { val numbers = input.readLine().split(" ").map { it.toInt() } val a = numbers[0] val b = numbers[1] val c = numbers[2] val d = numbers[3] val e = numbers[4] val f = numbers[5] for (x in -999..999) { for (y in -999..999) { if (a * x + b * y == c && d * x + e * y == f) { return "$x $y" } } } return "" } } |
연립방정식 풀이 사용
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
import java.io.BufferedReader fun main() { val input = System.`in`.bufferedReader() val output = System.out.bufferedWriter() output.write(No19532.solve(input)) input.close() output.flush() output.close() } object No19532 { fun solve(input: BufferedReader): String { val numbers = input.readLine().split(" ").map { it.toInt() } val a = numbers[0] val b = numbers[1] val c = numbers[2] val d = numbers[3] val e = numbers[4] val f = numbers[5] val x = (c * e - b * f) / (a * e - b * d) val y = (c * d - a * f) / (b * d - a * e) return "$x $y" } } |
결과
제출번호 62098145가 브루트 포스 알고리즘을 사용한 코드를 제출한 결과이고, 제출번호 62098191가 연립방정식을 사용한 코드를 제출한 결과입니다. 연립방정식을 사용한 코드가 메모리 사용량이나 처리 시간에서 조금 더 좋은 성능을 보이고 있습니다.
실행 결과
