백준 - 근손실(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

근손실이 없이 운동하는 방법을 구하시오.

 

[접근 방법]

완전 탐색으로 모든 경우의 수를 구하는 방법으로 풀었습니다.

시간복잡도는 O(N^N), 공간복잡도는 O(N)

N의 값은 1이상 8이하.

최악의 경우에도 8^8 => 2^24횟수가 연산이 됩니다.

log2이 0.3010.. => 24log2은 7.2이므로 최대 연산횟수는 8자리 숫자인 천만단위의 연산이 나온다.

import java.io.BufferedReader
import java.io.InputStreamReader


const val demandingWeight = 500
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var answer = 0
    val (N, K) = readLine().split(" ").map { it.toInt() }
    val isChecked = BooleanArray(N)
    val weights = readLine().split(" ").map { it.toInt() }.toIntArray()

    fun recursion(day: Int, currentWeight: Int) {
        // 현재 3대 중량이 500보다 작으면 함수 종료.
        if (currentWeight < demandingWeight) {
            return
        } else if (day == N + 1) {  // 마지막 날에 도달하면 조건을 만족하므로 경우의 수 증가.
            answer++
            return
        }

        weights.forEachIndexed { index, weight ->
            if (!isChecked[index]) {
                isChecked[index] = true
                recursion(day = day + 1, currentWeight = currentWeight + weight - K)
                isChecked[index] = false
            }
        }
    }

    recursion(day = 1, currentWeight = demandingWeight)
    println(answer)
}