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

문제

---

생각하기

---

• 배낭 문제이다

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

  • 인사를 하는 가지와 하지않는 가지 방향 모두 탐색해서 답을 찾는다.

동작

private fun solve(index: Int, nowHelth: Int, total: Int): Int {
    if (nowHelth >= 100) {
        return 0
    } else if (index == N) {
        return total
    }

    var ans = 0

    // 인사를 했을 때,
    ans = Math.max(ans, solve(index + 1, nowHelth + health[index], total + pleasure[index]))

    // 인사를 안 했을 때,
    ans = Math.max(ans, solve(index + 1, nowHelth, total))

    return ans
} // End of solve

재귀를 통한 구현으로 인사를 하는 메소드와 인사를 하지 않는 방향으로 매개변수를 통해 재귀 실행하여 최댓값을 도출해 낼 수 있다.

코드

---

Kotlin

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

private var N = 0
private val health = IntArray(21)
private val pleasure = IntArray(21)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`)

    N = br.readLine().toInt()

    var st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        health[i] = st.nextToken().toInt()
    }

    st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        pleasure[i] = st.nextToken().toInt()
    }

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

private fun solve(index: Int, nowHelth: Int, total: Int): Int {
    if (nowHelth >= 100) {
        return 0
    } else if (index == N) {
        return total
    }

    var ans = 0

    // 인사를 했을 때,
    ans = Math.max(ans, solve(index + 1, nowHelth + health[index], total + pleasure[index]))

    // 인사를 안 했을 때,
    ans = Math.max(ans, solve(index + 1, nowHelth, total))

    return ans
} // End of solve