1학년

기타리스트 문제와 비슷한 유형의 문제라고 볼 수 있다.

문제를 보면 숫자가 될 수 있는 범위는 0 ~ 20까지이고 수열의 길이는 최대 100개이므로 20*100, 즉 2,000개의 상태공간을 갖고 있음을 알 수 있다.

i번째 수를 N[i]라 하고, dp[i][n]을 i번째 수까지 계산했을 때, n이 나오는 경우의 수라고 하자.

맨 마지막이 L번째라고 한다면 우리가 구하고자 하는 값은 dp[L-1][N[L]]이라고 볼 수 있다. 즉, 맨 마지막 이전까지 계산했을 때 마지막 숫자가 나오는 경우를 찾으면 되는 것이다.

예를 들어 8 3 3 6 8이 주어졌다고 해보자. 그렇다면, 맨 앞자리는 무조건 시작하는 수이므로 dp[1][8] = 1임을 알 수 있다.

이제 dp[2]부터 계산을 시작하게 될텐데, +-N[i]를 했을 때 0부터 20까지 될 수 있는 경우의 수를 찾으면 된다.

단순하게 for문을 이용해서 구현할 수 있는데, 숫자가 0밑으로 가거나 20위로 올라가면 안되므로 N[i]를 기준으로 for문을 두 번 돌리면 답을 구할 수 있다.

정답

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 (
	nums []int
	dp   [][]int
)

func main() {
	N := scanInt()
	nums = make([]int, N+1)

	for ni := 1; ni <= N; ni++ {
		nums[ni] = scanInt()
	}

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

	dp[1][nums[1]] = 1

	for n := 2; n <= N; n++ {
		for num := nums[n]; num <= 20; num++ {
			dp[n][num] += dp[n-1][num-nums[n]]
		}

		for num := 0; num <= 20-nums[n]; num++ {
			dp[n][num] += dp[n-1][num+nums[n]]
		}
	}

	fmt.Println(dp[N-1][nums[N]])
}