백준 16493번
https://www.acmicpc.net/problem/16493

문제

---

생각하기

---

• 배낭 문제이다

• DP를 통해 풀이가 가능하다. 즉, memoization을 통한 최적화 가능

• 부르트포스 개념이 적용된다.

  • 책을 읽었을 때와 읽지 않았을 때를 구분하는 가지로 뻗어나가서 모두 탐색하여 최대값을 도출할 수 있다.

동작

private fun DFS(index: Int, day: Int, totalPages: Int): Int {
    if (index == M && day <= N) {
        return totalPages
    } else if (day > N) {
        // 연체 될 경우 무조건 return
        return 0
    }

    var ans = 0
    // 책을 읽었을 경우
    ans = Math.max(ans, DFS(index + 1, day + books[index].day, totalPages + books[index].page))

    // 책을 읽지 않았을 경우
    ans = Math.max(ans, DFS(index + 1, day, totalPages))

    return ans
} // End of DFS

책을 읽었을 때 와 읽지 않았을 때를 구분하여 재귀를 통해서 최대값을 찾는다.

재귀 탈출 조건은 index가 M에 도달했을 때, day가 N에 도달 했을 때 이다.

여기서 day를 증가시키다 보면 day는 N을 넘길 수 있게된다. 이 조건은 연체가 되는 경우이기 때문에 0을 return 하도록 한다.

index가 M이고 day가 N보다 작거나 같은 경우는 totalPages를 return 해준다.

코드

---

Kotlin

재귀를 통한 부르트포스

import java.util.*
import java.io.*

private var N = 0
private var M = 0
private lateinit var books: Array<Book>

data class Book(
    var day: Int = 0,
    var page: Int = 0
) // End of Book class

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 남은 기간
    M = st.nextToken().toInt() // 챕터 수
    books = Array(M) { Book() }

    // 남은 N일 동안, 책의 각 챕터 당 그 챕터를 전부 읽는데 소요되는 일 수와 페이지 수가 주어질 때, N일간 읽을 수 있는 최대 페이지 수를 구하시오
    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        books[i].day = st.nextToken().toInt()
        books[i].page = st.nextToken().toInt()
    }

    println(DFS(0, 0, 0))
} // End of main

private fun DFS(index: Int, day: Int, totalPages: Int): Int {
    if (index == M && day <= N) {
        return totalPages
    } else if (day > N) {
        // 연체 될 경우 무조건 return
        return 0
    }

    var ans = 0
    // 책을 읽었을 경우
    ans = Math.max(ans, DFS(index + 1, day + books[index].day, totalPages + books[index].page))

    // 책을 읽지 않았을 경우
    ans = Math.max(ans, DFS(index + 1, day, totalPages))

    return ans
} // End of DFS

Memoization을 활용한 DP

import java.util.*
import java.io.*

private var N = 0
private var M = 0
private var result = 0
private val memo = Array(22) { Array(302) { 0 } }
private val books = Array(22) { Book() }

private data class Book(var day: Int = 0, var page: Int = 0)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 남은 기간
    M = st.nextToken().toInt() // 챕터 수

    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        books[i].day = st.nextToken().toInt()
        books[i].page = st.nextToken().toInt()
    }

    DP()
    println(result)
} // End of main

private fun DP() {
    for (i in 0..M) {
        for (j in N downTo 0) {
            if (j - books[i].day >= 0) {
                memo[i + 1][j] = Math.max(memo[i][j], memo[i][j - books[i].day] + books[i].page)
            } else {
                memo[i + 1][j] = memo[i][j]
            }

            result = Math.max(result, memo[i][j])
        }
    }
} // End of DP