백준 - 퇴사(Kotlin 완전탐색으로 품)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

완전탐색 카테고리에서 고른 문제인데 동적프로그래밍으로 충분히 풀 수 있는 문제 같다.

완전탐색으로 풀고, 동적프로그래밍으로 풀어보려고 했는데 실패했다. 시간만 엄청 잡아 먹었다.

난이도가 절대 어려운 게 아닌데 동적프로그래밍을 거의 안풀어봐서 그런지 코드 짜기가 상당히 헷갈린다.

특히 N+1일까지 상담하는 것도 포함하는 것도 머리가 아프고, 끝나는 날을 체크하는 것도 굉장히 머리가 아프다.

오랜만에 알고리즘에서 엄청 막힌 문제 같다. 동적프로그래밍에 진짜 약해도 너무 약하다는 것을 느끼게 됐다.

동적프로그래밍 연습문제를 좀 풀어보고, 다시 풀어봐야겠다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
// 1. 완전탐색
// 2. DP
var sumOfCost = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val remainingDay = readLine().toInt()
    val arrOfTheDaysTake = IntArray(remainingDay)
    val arrOfCosts = IntArray(remainingDay)
    for (day in 0 until remainingDay) {
        val (period, cost) = readLine().split(" ").map { it.toInt() }
        arrOfTheDaysTake[day] = period
        arrOfCosts[day] = cost
    }

    getMaximumCost(arrOfTheDaysTake, arrOfCosts, 0, 0)
    println(sumOfCost)
}

fun getMaximumCost(arrOfTheDaysTake: IntArray, arrOfCosts: IntArray, currentDay: Int, currentCost: Int) {
    if (currentDay >= arrOfTheDaysTake.size) {
        sumOfCost = sumOfCost.coerceAtLeast(currentCost)
        return
    }

    val nextDay = currentDay + arrOfTheDaysTake[currentDay]
    if (nextDay <= arrOfTheDaysTake.size) {
        getMaximumCost(arrOfTheDaysTake, arrOfCosts, nextDay, currentCost+arrOfCosts[currentDay])
    }
    getMaximumCost(arrOfTheDaysTake, arrOfCosts, currentDay+1, currentCost)
}

---

계속 생각나고 스트레스 받아서 하루종일 잡고 동적프로그래밍으로 짜봤다.

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


var N = 0
var answer = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    N = readLine().toInt()
    val arrOfTheDaysTake = IntArray(N)
    val arrOfCosts = IntArray(N)
    for (day in  0 until N) {
        val (period, cost) = readLine().split(" ").map { it.toInt() }
        arrOfTheDaysTake[day] = period
        arrOfCosts[day] = cost
    }

    val dp = IntArray(arrOfTheDaysTake.size+1)
    getMaximumCost(arrOfTheDaysTake, arrOfCosts, 0, dp)
    println(answer)
}

fun getMaximumCost(arrOfTheDaysTake: IntArray, arrOfCosts: IntArray, currentDay: Int, dp: IntArray) {
    if (currentDay >= N) {
        return
    } else if (currentDay > 0) {
        dp[currentDay] = dp[currentDay].coerceAtLeast(dp[currentDay-1])
    }

    val nextDay = currentDay + arrOfTheDaysTake[currentDay]
    if (nextDay < N+1) {
        dp[nextDay] = dp[nextDay].coerceAtLeast(dp[currentDay]+arrOfCosts[currentDay])
        answer = answer.coerceAtLeast(dp[nextDay])
    }

    getMaximumCost(arrOfTheDaysTake, arrOfCosts, currentDay+1, dp)
}

 

[반성]

솔직히 아직도 긴가민가한다. 점화식을 찾는 건 괜찮았는데.

이 문제를 풀면서 제일 큰 문제 중에 하나는 나름대로 변수명을 의미 있게 준다고 했던 거에서 망했다.

점화식은 문제에서 주어진 N, T, P를 써서 풀었다.

그걸 코드로 옮기기 전에 나름 체크를 했어야 하는데, 무작정 짜다보니까 변수명이 헷갈리면서 시간을 엄청 뺏긴 거 같다.

 

난이도를 보고 안심하고 대충 푼 게 문제같다. 매번 나오는 반성이지만, 명확하게 생각을 하고 짜야한다.

물론, 생각만으로는 진행이 잘 안돼서 코드를 짜면서 스타트한 문제긴 하지만 그게 큰 화를 불렀던 거 같다.

동적프로그래밍 파트 앞으로 더 주의 깊게 봐야겠다.

 

새로운 카테고리 볼 때마다 낯설어서 안풀리고 짜증난 적이 많았긴 하지만, 이번 동적프로그래밍이 그 중에서도 역대급 최고로 스트레스 받는 거 같다.

그렇다고 놓으면 더 스트레스 받아서 계속 하는 수밖에 없어 보이지만