PS/BOJ

[BOJ/11058/Golang] 백준 11058 - 크리보드

wookiist 2021. 5. 16. 20:54
728x90

백준 11058 - 크리보드 [Gold/5] - Golang

접근 방식

DP로 접근할 수 있다. 힌트에도 주어져 있지만, 큰 문제를 작은 문제로 잘게 나누어 풀 수 있기 때문이다.

순서

TBD

코드

package main

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

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    D [101]int
    N int
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    N = scanInt()
    D[1], D[2], D[3] = 1, 2, 3
    for i := 4; i <= N; i++ {
        temp := 0
        for j := 1; j <= i-2; j++ {
            temp = max(temp, (j+1)*D[i-(j+2)])
        }
        D[i] = max(D[i-1]+1, temp)
    }
    fmt.Fprintln(w, D[N])
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

func max(arr ...int) int {
    res := arr[0]
    for i := range arr {
        if res < arr[i] {
            res = arr[i]
        }
    }
    return res
}
728x90
반응형