[BOJ] 1495번 : 기타리스트(Go, Golang)

문제 링크 : 백준 1495번

[문제 접근]

전부 탐색하게 되면 2의 100승으로 시간초과가 발생하게 된다.
나는 dp를 이용해서 풀었는데 dp[i][j]는 i번째 곡에서 볼륨 j로 연주할 수 있는지 없는지 판단하는 bool 배열이다.

처음 시작은 s에서 첫 볼륨을 더하고 빼면서 m보다 작거나 같고 0보다 크거나 같으면 true로 만들어준다.
그 다음 2번째 인덱스부터 n까지 탐색하는데 m까지가 가능한 볼륨 범위이므로 0~m까지 for문을 돌면서 전 곡에서(i-1) 연주한 볼륨이면(true) 현재 곡에서 +-arr[i]를 통해 m보다 작거나 같고 0보다 크거나 같으면 true로 변경하는 방식이다.

가능한 볼륨을 전부 true로 만들어준 후 n번째 곡에서 연주한 볼륨 중에 가장 큰 볼륨이 정답이므로 m부터 0까지 돌면서 dp[n][i]가 true가 나오면 i가 가장 큰 볼륨이다.

[소스 코드]

package main

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

var (
	r       = bufio.NewReader(os.Stdin)
	w       = bufio.NewWriter(os.Stdout)
	n, m, s int
	arr     [1001]int
	dp      [101][1001]bool // dp[i][j]는 i번째 곡에서 음량 j로 연주할 수 있다/없다.
)

func DP() int {
	// 처음 시작
	if s+arr[1] <= m {
		dp[1][s+arr[1]] = true
	}
	if s-arr[1] >= 0 {
		dp[1][s-arr[1]] = true
	}

	for i := 2; i <= n; i++ {
		for j := 0; j <= m; j++ { // 가능한 볼륨 범위
			if dp[i-1][j] { // 전 곡에서 연주한 볼륨
				if j+arr[i] <= m {
					dp[i][j+arr[i]] = true
				}
				if j-arr[i] >= 0 {
					dp[i][j-arr[i]] = true
				}
			}
		}
	}

	// n번째 곡에서 연주한 불륨중에 가장 큰 볼륨
	for i := m; i >= 0; i-- {
		if dp[n][i] {
			return i
		}
	}
	// n번째 곡에서 연주할 수 있는 볼륨이 없다면
	return -1
}

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n, &s, &m)
	for i := 1; i <= n; i++ {
		fmt.Fscan(r, &arr[i])
	}
	fmt.Fprintln(w, DP())
}