7490번: 0 만들기

문제 출처 : https://www.acmicpc.net/problem/7490

7490번: 0 만들기

언어 : Kotlin

 

문제 설명 :

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

 

입력 :

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

 

출력 :

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

입출력 예 :

입력	출력
2 3 7	1+2-3 1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7

 

풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

var arr = arrayOf<String>()

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val t = readLine().toInt()

    repeat(t) {
        if (it > 0) arr += ""
        isZero(1, readLine().toInt(), "1")
    }

    arr.forEach { bw.appendLine(it) }
    bw.flush()
    bw.close()
}

fun isZero(target: Int, n: Int, txt: String) {
    if (target == n) {
        val filteredNum = txt.replace(" ", "").split("[+\\-]".toRegex()).map { it.toInt() }.toMutableList()
        val filterdOperator = txt.replace(" ", "").split("[0-9]".toRegex()).filter { it.isNotEmpty() }

        for (i in filterdOperator.indices) {
            when (filterdOperator[i]) {
                "+" -> filteredNum[i + 1] = filteredNum[i] + filteredNum[i + 1]
                "-" -> filteredNum[i + 1] = filteredNum[i] - filteredNum[i + 1]
            }
        }
        if (filteredNum[filteredNum.lastIndex] == 0) arr += txt
        return
    }

    val next = target + 1
    isZero(target + 1, n, "$txt $next")
    isZero(target + 1, n, "$txt+$next")
    isZero(target + 1, n, "$txt-$next")
}