1학년

문제

풀이

처음엔 백트래킹으로 문제를 풀었다.
전형적인 백트래킹이라 생각하였고, 2 ** 100 이라는 큰 수지만 조건 때문에 줄어들지 않을까 생각하였다.
하지만 역시나 시간초과가 발생하였다.

이런 큰 연산을 처리하기 위해선 이전 값을 토대로 계산하는 DP 알고리즘을 사용해야 한다.
이전 값 = 이전 값 경우의 수

예제 입력 1 기준으로 생각하자면

이전의 값 경우의 수 + 8 = 8
or
이전의 값 경우의 수 - 8 = 8

이 될 것이다.
이전의 값 경우의 수는 다음과 같다.

이렇게 하여 8 -> 3 -> 2 -> 4 ... -> 8 까지 구한 후
해당 dp에서 8 인덱스를 구하면 된다.

def solution():
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    dp = [0 for _ in range(21)]

    for i in range(n - 1):
        tmp = [0 for _ in range(21)]
        if i == 0:
            dp[arr[0]] = 1
            continue
        for j in range(21):
            if dp[j] != 0:
                plus = arr[i] + j
                minus = j - arr[i]
                if 0 <= plus <= 20:
                    tmp[plus] += dp[j]
                if 0 <= minus <= 20:
                    tmp[minus] += dp[j]
        dp = tmp

    print(dp[arr[-1]])
solution()