paizaの練習問題を解く最安値を達成するには 2

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

最安値を達成するには 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

以下のように実装しました。

package main
import "fmt"
func main(){
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    dp := make([]int, n + 4)
    min := func(a, b int) int {
        if a < b {
            return a
        } else {
            return b
        }
    }
    dp[1] = a
    dp[2] = a
    dp[3] = min(a * 2, b)
    dp[4] = min(a * 2, b)
    for i := 5; i <= n + 3; i++ {
        dp[i] = min(dp[i - 2] + a, dp[i - 5] + b)
    }
    r := 0
    for i := 1; i < 5; i++ {
        r = min(dp[i - 1], dp[i])
    }
    fmt.Println(r)
}

ただ、これだと通りませんでした。

ということで解説を見てコードを修正しました。

package main
import "fmt"
func main(){
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    dp := make([]int, n + 5)
    min := func(a, b int) int {
        if a < b {
            return a
        } else {
            return b
        }
    }
    for i := 1; i < n + 5; i++ {
        dp[i] = 100000
    }
    for i := 5; i < n + 5; i++ {
        if i >= 2 {
            dp[i] = min(dp[i], dp[i - 2] + a)
        }
        if i >= 5 {
            dp[i] = min(dp[i], dp[i - 5] + b)
        }
    }

    dp2 := make([]int, n + 5)
    for i := n + 4; i >= 1; i-- {
        dp2[i] = dp[i]
        for j := i + 1; j < n + 5; j++ {
            dp2[i] = min(dp2[i], dp[j])
        }
    }
    fmt.Println(dp2[n])
}

しかし、これも通らず。。。

dpに入れている初期値が少なかったので、もう少し大きい値にしました。

package main
import "fmt"
func main(){
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    dp := make([]int, n + 5)
    min := func(a, b int) int {
        if a < b {
            return a
        } else {
            return b
        }
    }
    for i := 1; i < n + 5; i++ {
        dp[i] = 100000000
    }
    for i := 1; i < n + 5; i++ {
        if i >= 2 {
            dp[i] = min(dp[i], dp[i - 2] + a)
        }
        if i >= 5 {
            dp[i] = min(dp[i], dp[i - 5] + b)
        }
    }

    dp2 := make([]int, n + 5)
    for i := n + 4; i >= 1; i-- {
        dp2[i] = dp[i]
        for j := i + 1; j < n + 5; j++ {
            dp2[i] = min(dp2[i], dp[j])
        }
    }
    fmt.Println(dp2[n])
}

これで通りました。

もう少し短くしてみます。

package main
import "fmt"
func main(){
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    dp := make([]int, n + 5)
    min := func(a, b int) int {
        if a < b {
            return a
        } else {
            return b
        }
    }
    for i := 1; i < n + 5; i++ {
        dp[i] = 100000000
    }
    for i := 1; i < n + 5; i++ {
        if i >= 2 {
            dp[i] = min(dp[i], dp[i - 2] + a)
        }
        if i >= 5 {
            dp[i] = min(dp[i], dp[i - 5] + b)
        }
    }
    for i := n + 3; i >= 1; i-- {
        dp[i] = min(dp[i], dp[i + 1])
    }
    fmt.Println(dp[n])
}

これでも通りました。

ただ、なぜこれでちゃんと通るのかちゃんと理解できませんでした。。。やり直すしかねぇな！

では今回はこれで👍

実装#

実装