[Algorithm]BOJ_18809_앱 - Go

문제 링크

BOJ_18809_앱

생각

1. 생각해야 할 값이 2개다. 돌려받는 메모리와 리턴에 대한 오버헤드.
2. dp를 사용하는 가방 알고리즘을 떠올렸다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
)

var memories, returnVal []int
var table [][]int
var returnValMax int

func main() {
    r := bufio.NewReader(os.Stdin)
    var N, M int
    fmt.Fscan(r, &N, &M)
    memories = make([]int, N+1)
    returnVal = make([]int, N+1)
    for i := 1; i <= N; i++ {
        fmt.Fscan(r, &memories[i])
    }
    for i := 1; i <= N; i++ {
        fmt.Fscan(r, &returnVal[i])
        returnValMax += returnVal[i]
    }
    table = make([][]int, N+1)
    for i := 0; i <= N; i++ {
        table[i] = make([]int, returnValMax+1)
    }
    for y := 1; y <= N; y++ {
        for x := 0; x <= returnValMax; x++ {
            if x-returnVal[y] < 0 {
                table[y][x] = table[y-1][x]
            } else {
                table[y][x] = getMax(table[y-1][x], table[y-1][x-returnVal[y]]+memories[y])

            }
        }
    }
    for i := 0; i <= returnValMax; i++ {
        if table[N][i] >= M {
            fmt.Print(i)
            return
        }
    }
}

func getMax(a, b int) int {
    if a < b {
        return b
    }
    return a
}

결과