백준 1503 세 수 고르기 Kotlin (완전 탐색)

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

1503번: 세 수 고르기

문제

M개의 자연수로 이루어진 집합 S와 자연수 N이 주어진다.

S에 속하지 않는 자연수 x, y, z를 골라서, |N - xyz|의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어져 있다. 또, 중복되는 수는 없다.

집합의 크기가 0인 경우에는 둘째 줄은 빈 줄이다.

출력

첫째 줄에 |N - xyz|의 최솟값을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

정답 비율이 낮은 데에는 다 이유가 있다.

난이도에 비해 정답 비율이 낮은 경우 함정을 찾아야 한다.

본인은 이를 인지하고 있음에도 불구하고 당했다.

둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고

여기서 말하는 집합 S는 우리가 고를 수 있는 자연수 중 제외할 숫자들의 집합이다.

이 숫자들의 범위가 1~1000이고, 실제 우리가 고를 수 있는 자연수는 이 S에 들어있는 자연수들을 제외한 1부터 무한대까지의 자연수이다.

따라서 1001은 무조건 고를 수 있는 수이고, 무조건 고를 수 있는 수 중에서 가장 작은 값이기 때문에,

1부터 1001까지의 수를 3중 for문으로 완전 탐색하면 된다.

적절한 break문으로 시간을 더 줄일 수 있지만 문제에선 그런 걸 바라지 않았기 때문에 스킵.

이것은 실전 대비 전략이다.

 

코드

import java.lang.Math.abs
import java.util.*

val br = System.`in`.bufferedReader()
const val MAX = 1002

fun main() = with(System.out.bufferedWriter()){

    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val out = BooleanArray(MAX)
    if(m!=0) {
        val tk = StringTokenizer(br.readLine())
        while (tk.hasMoreTokens()) {
            out[tk.nextToken().toInt()] = true
        }
    }
    var answer =Int.MAX_VALUE

    for(i in 1 until MAX){
        if(out[i]) continue
        for(j in 1 until MAX){
            if(out[j]) continue
            for(k in 1 until MAX){
                if(out[k]) continue
                answer = answer.coerceAtMost(abs(n-i*j*k))
            }
        }
        if(answer==0) break
    }
    write("$answer")
    close()
}