백준 20167 꿈틀꿈틀 호석 애벌레 - 기능성 Kotlin (완전 탐색)

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

20167번: 꿈틀꿈틀 호석 애벌레 - 기능성

문제

꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 또한 매초 1 만큼 오른쪽으로 무조건 진행한다.

호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 최소 만족도 K  이상이 되거나 더 이상 먹을 먹이가 없을 때에 연속적으로 먹는 것을 멈춘다. 만약 최소 만족도 이상이 되면 K 를 초과한 만족도만큼 탈피 에너지를 축적한다. 직후에 호석 애벌레의 만족도는 다시 0 이 되고 먹이를 먹을 수 있게 된다. 나뭇가지를 전부 통과했을 때에 소화를 다 못 했을 경우에도 탈피 에너지는 최소 만족도를 넘기는 순간 이미 축적한 것으로 생각하자.

예를 들어 위와 같이 9개의 먹이가 존재하면, 호석 애벌레는 미래를 도모하여 1번 먹이를 과감하게 포기한다. 그리고 2번부터 먹기 시작해서 3번까지 먹으면 만족도가 9가 되어 3의 에너지를 축적하게 된다. 같은 이유로 4번 먹이도 포기하고 5번부터 먹으면 7번까지 연속으로 먹어서 15의 만족도를 얻는다. 이를 통해 9의 탈피 에너지가 쌓인다. 8, 9번 먹이까지 먹게 되면 2의 탈피 에너지가 축적된다. 이렇게 얻은 총 14의 탈피 에너지가 위의 예제에서는 최대치이다.

매초마다 호석 애벌레는 오른쪽으로 이동하면서 먹이를 지나치거나 먹기 시작할 수 있다. 먹기 시작하면 만족도가 채워질때까지 먹게 될것이다. 어떤 먹이들을 대해 먹어야 축적된 탈피 에너지가 최대가 될 수 있을까?

입력

첫번째 줄에 먹이 개수 N, 최소 만족도 K 가 공백으로 주어진다.

두번째 줄에는 1 번부터 N 번 먹이의 만족도가 순서대로 주어진다.

출력

축적된 탈피 에너지의 최댓값을 구하라. 만약 탈피를 한 번도 할 수 없다면 0을 출력한다.

제한

• 1 ≤ N ≤ 20, N 은 정수이다.
• 1 ≤ K ≤ 100, K 는 정수이다.
• 0 ≤ 각 먹이의 만족도 ≤ 100, 모든 만족도는 정수이다.

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘

풀이

N이 20이라 가볍게 dfs로 완전 탐색하면 된다.

dfs의 탐색 가지는 현재 먹는 중이면 계속 먹어야 하고, 먹고 있지 않다면 현재 칸을 먹는 경우, 먹지 않는 경우 두 가지가 있다.

현재 칸을 먹고 누적 만족도가 k이상이 된다면 eating(먹고 있는지 상태 값)을 false로 넘긴다.

크게 먹고 있는 상태, 안 먹고 있는 상태 두 개를 분기하여 코드를 작성했는데 이 분기를  안 쪽으로 옮기면 더 깔끔한 코드 작성이 가능하다.

탐색 종료 조건은 현재 탐색 인덱스가 n에 도달했을 때이고, 이때 정답을 최댓값으로 갱신해 준다.

 

2022.05.16 - [알고리즘 문제 풀이/백준] - 백준 20181 꿈틀꿈틀 호석 애벌레 - 효율성 Kotlin (투 포인터)

이 풀이로는 위의 효율성 문제는 통과하지 못한다.

그렇다고 이 풀이가 좋지 못한 풀이인가?

이 문제 한정으론 좋은 풀이이다. 아니 내 풀이가 좋은 풀이라는 건 아니고, 코테 대비 알고리즘 문제 풀이는
주어진 조건에 맞게 좀 더 빠르게 풀 수 있다면 빠르게 풀고 다음 문제를 풀자는 말이다~

 

 

코드

val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
/*
* N개의 먹이
* 0부터 시작, 매초 1만큼 오른쪽으로 이동
* 최소 만족도 k이상 되거나 먹이가 없을 때는 그만 먹음 -> 다음 칸을 먹을지, 패스할지 선택 가능한 상태
* 탈피에너지 = 현재 연속 먹은 값 - 최소 만족도 만큼
* 애벌레 먹은 값 0으로 초기화
* 그래프의 끝에 도달했을 때는 남아있는 먹은값을 탈피에너지 계산해서 축적
* 현재 칸을 먹느냐 안 먹느냐 -> k보다 큰 값이 나올 때 얼마나 큰 값이 나올지로 판단
* */
lateinit var graph: List<Int>
var answer = 0

fun backTracking(n: Int,k: Int,idx: Int, eating: Boolean,cost: Int,result: Int){
    if(idx==n){
        answer = answer.coerceAtLeast(result)
        return
    }
    //아직 안 먹는중
    if(!eating){
        //안 먹을래~
        backTracking(n,k,idx+1,false, cost, result)
        //먹을래~
        val nextCost = cost + graph[idx]
        //만족해~
        if (nextCost >= k) {
            backTracking(n, k, idx + 1, false, 0, result + nextCost - k)
        }
        //아직이야~
        else {
            backTracking(n, k, idx + 1, true, nextCost, result)
        }
    }
    //먹는중
    else {
        val nextCost = cost + graph[idx]
        //만족해~
        if (nextCost >= k) {
            backTracking(n, k, idx + 1, false, 0, result + nextCost - k)
        }
        //아직이야~
        else {
            backTracking(n, k, idx + 1, true, nextCost, result)
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n, k) = getIntList()
    graph = getIntList()

    //solve
    backTracking(n,k,0,false,0,0)
    //output
    write("$answer")

    close()
}