기타리스트

• 곡의 갯수 N개
• 시작 볼륨 S
• 최대 볼륨 M

완전탐색으로 생각해보자. 각 곡마다 볼륨값을 선택(높이거나 낮추거나)해보고, 끝까지 선택했을 때 볼륨의 최댓값을 저장하여 보여주면 된다. 하지만 이렇게 하는 경우 단순하게 계산했을 때 최악의 경우 O(2^N)이 된다.

문제에서 볼륨의 범위는 0~1000까지라고 했다. 즉, 중간과정 어떤 값이든 볼륨의 범위는 0~1000이 된다.

곡의 갯수는 최대 100이다. 따라서, 이 문제에서는 모든 곡마다 가질 수 있는 볼륨의 상태 공간의 갯수는 100*1000 = 100,000이다.

이런 문제를 푸는 방법 중 대표적인 것이 바로 DP이다.

DP로 문제를 접근해보면, N번째 곡의 볼륨이 0~1000이 될 수 있는가를 계산해보면 된다.

즉, dp[N][V]를 N번째 곡에서 볼륨 V가 될 수 있는지로 정의하고, V[N]을 N번째 곡에서의 볼륨조절량이라고 했을 때, N번째 곡에서 볼륨 V가 될 수 있는지 그 여부는 N-1번째 곡에서 V-V[N] 혹은 V+V[N]의 볼륨이 될 수 있는지 여부에 달려있다.

전형적인 DP문제로 코드로 구현하면 된다.

답(bottom-up)

package main

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

var sc *bufio.Scanner

func init() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
}

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

var (
    N, S, M int
    V       []int
    dp      [][]bool
)

func main() {
    N, S, M = scanInt(), scanInt(), scanInt()
    V = make([]int, N+1)

    for vi := 1; vi <= N; vi++ {
        V[vi] = scanInt()
    }

    dp = make([][]bool, N+1)
    for di := range dp {
        dp[di] = make([]bool, M+1)
    }

    // 0번째 곡은 시작볼륨이다.
    dp[0][S] = true

    for n := 1; n <= N; n++ {
        for v := 0; v <= M; v++ {
            
            if dp[n-1][v] {
                // n-1번째 곡이 볼륨 v일 때, n번째 곡이
                // 해당 볼륨에 V[n]을 더했을 때
                // 최대 볼륨 M을 넘지 않는 경우
                // v+V[n] 볼륨에 도달 할 수 있다.
                if v + V[n] <= M {
                    dp[n][v+V[n]] = true
                }

                if v - V[n] >= 0 {
                    dp[n][v-V[n]] = true
                }
            }
        }
    }

    for v := M; v >= 0; v-- {
        if dp[N][v] {
            fmt.Println(v)
            return
        }
    }

    // 도달할 수 있는 볼륨이 없는 경우
    // -1
    fmt.Println(-1)
}

답(top-down)

package main

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

var sc *bufio.Scanner

func init() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
}

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

var (
	dp      [][]int
	V       []int
	N, S, M int

)

const (
	none = iota
	impossible
	possible
)

func main() {
	N, S, M = scanInt(), scanInt(), scanInt()
	V = make([]int, N+1)

	for vi := 1; vi <= N; vi++ {
		V[vi] = scanInt()
	}

	dp = make([][]int, N+1)
	for di := range dp {
		dp[di] = make([]int, M+1)
	}

	for v := M; v >= 0; v-- {
		if isPossible(N, v) == possible {
			fmt.Println(v)
			return
		}
	}

	fmt.Println(-1)
}

// i번째 곡이 volume에 도달할 수 있는가?
func isPossible(i, volume int) int {
	if i == 0 {
		if volume == S {
			return possible
		}

		return impossible
	}

	if volume > M || volume < 0 {
		return impossible
	}

	ret := &dp[i][volume]
	if *ret != none {
		return *ret
	}

	*ret = or(isPossible(i-1, volume-V[i]), isPossible(i-1, volume+V[i]))
	return *ret
}

func or(a, b int) int {
	if a == possible || b == possible {
		return possible
	}

	return impossible
}