백준 반례 찾는 방법 (코틀린)

백준에서 가장 곤란한 점 중 하나는 틀린 경우 틀렸습니다. 라고만 알려주고 어떤 입력에서 틀렸는지 알려주지 않는다는 점입니다. 이는 비단 백준만의 문제가 아니라 거의 모든 온라인 저지 사이트가 그렇습니다.

해당 코드가 어떤 인풋에서 틀렸는지를 알려주면, 그 사이트에서 사용하는 테스트 케이스가 뭐가 있는지 모두 알아낼 수 있다는 뜻이고, 그럼 그냥 알고리즘이고 뭐고 if문으로 모든 input마다 분기를 나눠서 단순히 정답을 print해버리면 모든 문제가 간단히 파훼 되어버리기 때문에 알려주지 않습니다.

 

그 덕분에 순수하게 내 코드가 왜 틀렸는지, 반례가 뭔지 알고 싶은 사람들에겐 답답한 상황이 나옵니다.

그래서 제가 쓰는 방법은 인풋을 랜덤하게 대입하고, 제 코드랑 인터넷에 있는 정답 코드랑 비교해서 다른 답이 나올 때까지 루프를 돌리는 겁니다.

 

* 아래의 코드들은 백준에서 쓰는 게 아니라 별도로 구축한 IDE에서 코드를 쓰는 겁니다. 백준에서 이 코드 복붙해봤자 당연히 틀렸다고만 하고 출력을 안 알려줍니다. 저는 IntelliJ를 사용했습니다.

 

반례 생성기 기본 구조

제가 예전에 하루동안 고생했던 1002번 문제를 예로 들게요.

 

반례 생성기의 기본 구조는 이렇습니다.

import java.awt.Toolkit
import java.awt.datatransfer.Clipboard
import java.awt.datatransfer.StringSelection
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.random.Random




var myAnswer = 0
var internetAnswer = 0

fun main() {

	var count = 0
    while (true) {
        val input = StringBuilder()
        
        // ==== 문제의 조건에 맞는 인풋 생성 ===== //
        TODO("문제 조건에 맞는 인풋을 만들어 input에 넣어주세요.")

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))

        if (myAnswer != internetAnswer) {
            println("반례를 찾았습니다.")
            println(input)
            println("myAnswer: $myAnswer internetAnswer: $internetAnswer")
            setClipboard(input.toString())
            break
        } else {
        	println("반례를 찾는 중입니다: $count++")
        }
    }

}

fun setClipboard(s: String) {
    val selection = StringSelection(s)
    val clipboard: Clipboard = Toolkit.getDefaultToolkit().systemClipboard
    clipboard.setContents(selection, selection)
}

// ===== 자신의 코드 ===== //
TODO("자신의 코드를 복붙하고 fun main()을 fun main2(br: BufferedReader) = with(br)로 변경하세요.")

// ===== 정답 코드 ===== //
TODO("인터넷에서 찾은 정답 코드를 복붙하고 fun main()을 fun main3(br: BufferedReader) = with(br)로 변경하세요.")

 

자신의 코드

자신의 코드라고 주석이 적힌 곳에 제 코드를 복사 붙여넣기 합니다.

import java.awt.Toolkit
import java.awt.datatransfer.Clipboard
import java.awt.datatransfer.StringSelection
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.random.Random




var myAnswer = 0
var internetAnswer = 0

fun main() {

    while (true) {
        val input = StringBuilder()
        
        // ==== 문제의 조건에 맞는 인풋 생성 ===== //

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))

        if (myAnswer != internetAnswer) {
            println("반례를 찾았습니다.")
            println(input)
            println("myAnswer: $myAnswer internetAnswer: $internetAnswer")
            setClipboard(input.toString())
            break
        }
    }

}

fun setClipboard(s: String) {
    val selection = StringSelection(s)
    val clipboard: Clipboard = Toolkit.getDefaultToolkit().systemClipboard
    clipboard.setContents(selection, selection)
}

// ===== 자신의 코드 ===== //
fun main2(br: BufferedReader) = with(br) {
    repeat(readLine()!!.toInt()) {
        val inputs = readLine()!!.split(" ").map { it.toInt() }

        // 두 원의 방정식을 연립해서 (dx + ey = f) == (y = (f - dx) / e) 꼴로 변형
        val d = 2 * (inputs[3] - inputs[0])
        val e = 2 * (inputs[4] - inputs[1])
        val f = (inputs[2] * inputs[2]) - (inputs[5] * inputs[5]) - (inputs[0] * inputs[0]) + (inputs[3] * inputs[3]) - (inputs[1] * inputs[1]) + (inputs[4] * inputs[4])

        var a = 0.0
        var b = 0.0
        var c = 0.0

        if (e != 0) { // 일반적인 경우 (dx + ey = f)
            // y = (f - dx) / e를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ax^2 + bx + c = 0로 변경
            a = 1 + (d * d).toDouble() / (e * e)
            b = (-2 * inputs[0]) + (2 * -(d.toDouble() / e) * (f.toDouble() / e - inputs[1]))
            c = (inputs[0] * inputs[0]) + ((f.toDouble() / e - inputs[1]) * (f.toDouble() / e - inputs[1])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d != 0 && e == 0) { // e가 0인 경우 (dx = f)
            // x = f / d를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ay^2 + by + c = 0로 변경
            a = 1.0
            b = -2 * inputs[1].toDouble()
            c = (inputs[1] * inputs[1]) + ((f.toDouble() / d - inputs[0]) * (f.toDouble() / d - inputs[0])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d == 0 && e == 0) { // d와 e가 0인 경우 (0 = f)
            if (f == 0) { // 원이 완벽히 겹침 (무한개)
                println(-1)
            } else { // 원의 중심은 겹치나 반지름이 다름
                println(0)
            }
        }
    }
}

// 판별식 D = b^2 -4ac
fun D(a: Double, b: Double, c: Double) {
    val D = (b * b) - (4 * a * c)
    if (D == 0.0) {
        println(1)
    } else if (D > 0.0) {
        println(2)
    } else {
        println(0)
    }
}

// ===== 정답 코드 ===== //

이때 붙여넣은 제 코드의 fun main()을 다음과 같이 바꿉니다.

// ===== 자신의 코드 ===== //
fun main2(br: BufferedReader) = with(br) {
    ...

main을 main2로 바꾸고, 인자로 BufferedReader를 받습니다.

그리고 = with(br)를 옆에 써줍니다.

 

이제 인터넷에서 정답 코드를 가져옵니다.

구글에 백준 + 해당 문제 번호 + 코틀린이라고 검색하면 1002번 문제를 코틀린으로 푼 다른 분들의 문제가 나옵니다.

코틀린은 아직까지 백준에서 비주류 언어라서 코틀린 코드가 없을 수도 있습니다. 그럴 때는 그냥 자바의 코드를 복붙하면 intelliJ에서 알아서 코틀린으로 번역을 해줍니다.

 

복사한 코드를 반례 생성기의 정답 코드 주석 뒤에 붙여넣습니다.

import java.awt.Toolkit
import java.awt.datatransfer.Clipboard
import java.awt.datatransfer.StringSelection
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.random.Random

import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt




var myAnswer = 0
var internetAnswer = 0

fun main() {

    while (true) {
        val input = StringBuilder()
        
        // ==== 문제의 조건에 맞는 인풋 생성 ===== //

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))

        if (myAnswer != internetAnswer) {
            println("반례를 찾았습니다.")
            println(input)
            println("myAnswer: $myAnswer internetAnswer: $internetAnswer")
            setClipboard(input.toString())
            break
        }
    }

}

fun setClipboard(s: String) {
    val selection = StringSelection(s)
    val clipboard: Clipboard = Toolkit.getDefaultToolkit().systemClipboard
    clipboard.setContents(selection, selection)
}

// ===== 자신의 코드 ===== //
fun main2(br: BufferedReader) = with(br) {
    repeat(readLine()!!.toInt()) {
        val inputs = readLine()!!.split(" ").map { it.toInt() }

        // 두 원의 방정식을 연립해서 (dx + ey = f) == (y = (f - dx) / e) 꼴로 변형
        val d = 2 * (inputs[3] - inputs[0])
        val e = 2 * (inputs[4] - inputs[1])
        val f = (inputs[2] * inputs[2]) - (inputs[5] * inputs[5]) - (inputs[0] * inputs[0]) + (inputs[3] * inputs[3]) - (inputs[1] * inputs[1]) + (inputs[4] * inputs[4])

        var a = 0.0
        var b = 0.0
        var c = 0.0

        if (e != 0) { // 일반적인 경우 (dx + ey = f)
            // y = (f - dx) / e를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ax^2 + bx + c = 0로 변경
            a = 1 + (d * d).toDouble() / (e * e)
            b = (-2 * inputs[0]) + (2 * -(d.toDouble() / e) * (f.toDouble() / e - inputs[1]))
            c = (inputs[0] * inputs[0]) + ((f.toDouble() / e - inputs[1]) * (f.toDouble() / e - inputs[1])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d != 0 && e == 0) { // e가 0인 경우 (dx = f)
            // x = f / d를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ay^2 + by + c = 0로 변경
            a = 1.0
            b = -2 * inputs[1].toDouble()
            c = (inputs[1] * inputs[1]) + ((f.toDouble() / d - inputs[0]) * (f.toDouble() / d - inputs[0])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d == 0 && e == 0) { // d와 e가 0인 경우 (0 = f)
            if (f == 0) { // 원이 완벽히 겹침 (무한개)
                println(-1)
            } else { // 원의 중심은 겹치나 반지름이 다름
                println(0)
            }
        }
    }
}

// 판별식 D = b^2 -4ac
fun D(a: Double, b: Double, c: Double) {
    val D = (b * b) - (4 * a * c)
    if (D == 0.0) {
        println(1)
    } else if (D > 0.0) {
        println(2)
    } else {
        println(0)
    }
}

// ===== 정답 코드 ===== //

fun main3(br: BufferedReader) = with(br) {
    val n = readLine()!!.toInt()
    for (i: Int in 1..n) {
        val info = readLine()!!.split(" ")
        val typeChange = change(info)
        val result = tangentPoint(typeChange)
        println(result)
    }
}

fun change(argument: List<String>): ArrayList<Double> {
    val array = ArrayList<Double>()
    for(i in argument.indices) array.add(argument.get(i).toDouble())
    return array
}

fun tangentPoint(info: List<Double>): Int {
    val distance = sqrt((info[3] - info[0]).pow(2) + (info[4] - info[1]).pow(2))
    return if (info[0] == info[3] && info[1] == info[4] && info[2] == info[5]) -1
    else if (distance > (info[2] + info[5]) || (info[0] == info[3] && info[1] == info[4] && info[2] != info[5]) || distance < abs(info[2] - info[5])) 0
    else if (distance == (info[2] + info[5]) || distance == abs(info[2] - info[5])) 1
    else 2
}

이때, import는 전부 코드의 제일 위로 올려주고

fun main은 다음과 같이 바꿉니다.

// ===== 정답 코드 ===== //
fun main3(br: BufferedReader) = with(br) {
	...

 

출력 비교

import java.awt.Toolkit
import java.awt.datatransfer.Clipboard
import java.awt.datatransfer.StringSelection
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.random.Random

import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt




var myAnswer = 0
var internetAnswer = 0

fun main() {

    while (true) {
        val input = StringBuilder()
        
        // ==== 문제의 조건에 맞는 인풋 생성 ===== //

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))

        if (myAnswer != internetAnswer) {
            println("반례를 찾았습니다.")
            println(input)
            println("myAnswer: $myAnswer internetAnswer: $internetAnswer")
            setClipboard(input.toString())
            break
        }
    }

}

fun setClipboard(s: String) {
    val selection = StringSelection(s)
    val clipboard: Clipboard = Toolkit.getDefaultToolkit().systemClipboard
    clipboard.setContents(selection, selection)
}

// ===== 자신의 코드 ===== //
fun main2(br: BufferedReader) = with(br) {
    repeat(readLine()!!.toInt()) {
        val inputs = readLine()!!.split(" ").map { it.toInt() }

        // 두 원의 방정식을 연립해서 (dx + ey = f) == (y = (f - dx) / e) 꼴로 변형
        val d = 2 * (inputs[3] - inputs[0])
        val e = 2 * (inputs[4] - inputs[1])
        val f = (inputs[2] * inputs[2]) - (inputs[5] * inputs[5]) - (inputs[0] * inputs[0]) + (inputs[3] * inputs[3]) - (inputs[1] * inputs[1]) + (inputs[4] * inputs[4])

        var a = 0.0
        var b = 0.0
        var c = 0.0

        if (e != 0) { // 일반적인 경우 (dx + ey = f)
            // y = (f - dx) / e를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ax^2 + bx + c = 0로 변경
            a = 1 + (d * d).toDouble() / (e * e)
            b = (-2 * inputs[0]) + (2 * -(d.toDouble() / e) * (f.toDouble() / e - inputs[1]))
            c = (inputs[0] * inputs[0]) + ((f.toDouble() / e - inputs[1]) * (f.toDouble() / e - inputs[1])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d != 0 && e == 0) { // e가 0인 경우 (dx = f)
            // x = f / d를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ay^2 + by + c = 0로 변경
            a = 1.0
            b = -2 * inputs[1].toDouble()
            c = (inputs[1] * inputs[1]) + ((f.toDouble() / d - inputs[0]) * (f.toDouble() / d - inputs[0])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d == 0 && e == 0) { // d와 e가 0인 경우 (0 = f)
            if (f == 0) { // 원이 완벽히 겹침 (무한개)
//                println(-1)
                myAnswer = -1
            } else { // 원의 중심은 겹치나 반지름이 다름
//                println(0)
                myAnswer = -1
            }
        }
    }
}

// 판별식 D = b^2 -4ac
fun D(a: Double, b: Double, c: Double) {
    val D = (b * b) - (4 * a * c)
    if (D == 0.0) {
//        println(1)
        myAnswer = 1
    } else if (D > 0.0) {
//        println(2)
        myAnswer = 2
    } else {
//        println(0)
        myAnswer = 0
    }
}

// ===== 정답 코드 ===== //
fun main3(br: BufferedReader) = with(br) {
    val n = readLine()!!.toInt()
    for (i: Int in 1..n) {
        val info = readLine()!!.split(" ")
        val typeChange = change(info)
        val result = tangentPoint(typeChange)
//        println(result)
        internetAnswer = result
    }
}

fun change(argument: List<String>): ArrayList<Double> {
    val array = ArrayList<Double>()
    for(i in argument.indices) array.add(argument.get(i).toDouble())
    return array
}

fun tangentPoint(info: List<Double>): Int {
    val distance = sqrt((info[3] - info[0]).pow(2) + (info[4] - info[1]).pow(2))
    return if (info[0] == info[3] && info[1] == info[4] && info[2] == info[5]) -1
    else if (distance > (info[2] + info[5]) || (info[0] == info[3] && info[1] == info[4] && info[2] != info[5]) || distance < abs(info[2] - info[5])) 0
    else if (distance == (info[2] + info[5]) || distance == abs(info[2] - info[5])) 1
    else 2
}

마지막으로 자신의 코드와 인터넷 코드 둘 다 정답을 출력하는 부분을 정답을 myAnswer와 internetAnswer에 넣습니다.

자신의 코드 정답은 myAnswer에

인터넷 코드 정답은 internetAnswer에 대입합니다.

 

랜덤 인풋 생성 코드 작성

마지막으로 랜덤한 인풋을 생성하는 코드를 '문제의 조건에 맞는 인풋 생성' 주석 쪽에 작성합니다.

1002번 문제의 경우 첫 인풋은 테스트 케이스의 개수이므로 그냥 1으로 해도 상관 없고 (어차피 랜덤 인풋 생성기가 while문으로 무한 루프 돌리기 때문)

2번째 라인에 6개의 숫자가 들어오는데

네 뭐 이런 조건이라네요. 여기에 맞춰서 코드를 작성합니다.

fun main() {

    while (true) {
        val input = StringBuilder()

        // ===== 문제의 조건에 맞는 인풋 생성 ===== //
        input.append("1\n")
        input.append("${Random.nextInt(20001) - 10000} ${Random.nextInt(20001) - 10000} ${Random.nextInt(10000) + 1} ${Random.nextInt(20001) - 10000} ${Random.nextInt(20001) - 10000} ${Random.nextInt(10000) + 1}\n")

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        
        ...

input에다가 append를 통해 문제의 조건에 맞게 랜덤 숫자들을 추가합니다.

String을 안 쓴 이유는 인풋이 정말 많이 들어가는 문제들의 경우 (ex - 수 만개의 숫자를 인풋으로 주고 정렬 시키라고 시키는 경우) String에 계속 += 하면 성능이 급격히 떨어지기 때문에

String Builder를 이용하였습니다.

 

전체 코드는 다음과 같습니다.

import java.awt.Toolkit
import java.awt.datatransfer.Clipboard
import java.awt.datatransfer.StringSelection
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.random.Random

import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt




var myAnswer = 0
var internetAnswer = 0

fun main() {

    while (true) {
        val input = StringBuilder()

        // ===== 문제의 조건에 맞는 인풋 생성 ===== //
        input.append("1\n")
        input.append("${Random.nextInt(20001) - 10000} ${Random.nextInt(20001) - 10000} ${Random.nextInt(10000) + 1} ${Random.nextInt(20001) - 10000} ${Random.nextInt(20001) - 10000} ${Random.nextInt(10000) + 1}\n")

        main2(BufferedReader(InputStreamReader(input.toString().byteInputStream())))
        main3(BufferedReader(InputStreamReader(input.toString().byteInputStream())))

        if (myAnswer != internetAnswer) {
            println("반례를 찾았습니다.")
            println(input)
            println("myAnswer: $myAnswer internetAnswer: $internetAnswer")
            setClipboard(input.toString())
            break
        }
    }

}

fun setClipboard(s: String) {
    val selection = StringSelection(s)
    val clipboard: Clipboard = Toolkit.getDefaultToolkit().systemClipboard
    clipboard.setContents(selection, selection)
}

// ===== 자신의 코드 ===== //
fun main2(br: BufferedReader) = with(br) {
    repeat(readLine()!!.toInt()) {
        val inputs = readLine()!!.split(" ").map { it.toInt() }

        // 두 원의 방정식을 연립해서 (dx + ey = f) == (y = (f - dx) / e) 꼴로 변형
        val d = 2 * (inputs[3] - inputs[0])
        val e = 2 * (inputs[4] - inputs[1])
        val f = (inputs[2] * inputs[2]) - (inputs[5] * inputs[5]) - (inputs[0] * inputs[0]) + (inputs[3] * inputs[3]) - (inputs[1] * inputs[1]) + (inputs[4] * inputs[4])

        var a = 0.0
        var b = 0.0
        var c = 0.0

        if (e != 0) { // 일반적인 경우 (dx + ey = f)
            // y = (f - dx) / e를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ax^2 + bx + c = 0로 변경
            a = 1 + (d * d).toDouble() / (e * e)
            b = (-2 * inputs[0]) + (2 * -(d.toDouble() / e) * (f.toDouble() / e - inputs[1]))
            c = (inputs[0] * inputs[0]) + ((f.toDouble() / e - inputs[1]) * (f.toDouble() / e - inputs[1])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d != 0 && e == 0) { // e가 0인 경우 (dx = f)
            // x = f / d를 (x - x1)^2 + (y - y1)^2 = (r1)^2에 대입하여 ay^2 + by + c = 0로 변경
            a = 1.0
            b = -2 * inputs[1].toDouble()
            c = (inputs[1] * inputs[1]) + ((f.toDouble() / d - inputs[0]) * (f.toDouble() / d - inputs[0])) - (inputs[2] * inputs[2])
            D(a, b, c)
        } else if (d == 0 && e == 0) { // d와 e가 0인 경우 (0 = f)
            if (f == 0) { // 원이 완벽히 겹침 (무한개)
//                println(-1)
                myAnswer = -1
            } else { // 원의 중심은 겹치나 반지름이 다름
//                println(0)
                myAnswer = -1
            }
        }
    }
}

// 판별식 D = b^2 -4ac
fun D(a: Double, b: Double, c: Double) {
    val D = (b * b) - (4 * a * c)
    if (D == 0.0) {
//        println(1)
        myAnswer = 1
    } else if (D > 0.0) {
//        println(2)
        myAnswer = 2
    } else {
//        println(0)
        myAnswer = 0
    }
}

// ===== 정답 코드 ===== //
fun main3(br: BufferedReader) = with(br) {
    val n = readLine()!!.toInt()
    for (i: Int in 1..n) {
        val info = readLine()!!.split(" ")
        val typeChange = change(info)
        val result = tangentPoint(typeChange)
//        println(result)
        internetAnswer = result
    }
}

fun change(argument: List<String>): ArrayList<Double> {
    val array = ArrayList<Double>()
    for(i in argument.indices) array.add(argument.get(i).toDouble())
    return array
}

fun tangentPoint(info: List<Double>): Int {
    val distance = sqrt((info[3] - info[0]).pow(2) + (info[4] - info[1]).pow(2))
    return if (info[0] == info[3] && info[1] == info[4] && info[2] == info[5]) -1
    else if (distance > (info[2] + info[5]) || (info[0] == info[3] && info[1] == info[4] && info[2] != info[5]) || distance < abs(info[2] - info[5])) 0
    else if (distance == (info[2] + info[5]) || distance == abs(info[2] - info[5])) 1
    else 2
}

 

반례 찾기 시작

이제 준비를 끝났습니다.

코드를 돌리면 경우에 따라 반례가 바로 나올 수도 있고 진짜 한참 걸릴 수도 있습니다.

 

제 경우엔 알고리즘은 맞는데 특정 인풋 값이 들어올 경우 부동 소수점 정확도 문제로 틀리는 케이스였기 때문에 정말 오래 걸렸습니다. 한 3분 지켜보다가 그냥 화장실 갔다 왔더니 그제서야 반례가 나오더라구요.

반례가 나왔을 당시 인풋이 뭔지, 내 정답은 뭐고 인터넷 정답은 뭔지 알려줍니다.

또한 반례가 나오는 순간 자동으로 클립보드에 인풋이 들어가게 되어있기 때문에 (setClipboard 함수 부분) 컨트롤+V로 바로 반례를 복붙할 수도 있습니다.