A - Contest

- $\operatorname{dp}[i][s]$를 $i$번째 질문까지 고려했을 때 $s$점을 획득할 수 있으면 $\text{True}$, 아니면 $\text{False}$로 정의하자. 그럼 점화식은 다음과 같다

- $\operatorname{dp}[i][s] = \operatorname{dp}[i - 1][s] \lor \operatorname{dp}[i - 1][s - p_i]$. base case로 $\operatorname{dp}[0][0] = \text{True},\, \operatorname{dp}[i][p_i] = \text{True}$이며 정답은 $\sum \operatorname{dp}[N]$이다

- 문제 조건에서 $p_i \le 100$이므로 최대 획득 점수는 $100N$에 바운드된다. 따라서 전체 알고리즘의 시간 복잡도는 $O\left(100N^2\right)$이다

- 배낭 용량과 물건 가치는 고려하지 않고 만들 수 있는 배낭 무게의 가짓수만 관심있는 배낭 문제라고 생각할 수 있겠다~

def solution():
    N = int(input())
    array = list(map(int, input().split()))
    max_score = 100 * N
    dp = [0] * (max_score + 1)
    dp[0] = 1 
    for i in range(N):
        p_i = array[i]
        for s in range(max_score, p_i, -1):
            dp[s] |= dp[s - p_i]
        dp[p_i] = 1
    answer = sum(dp)
    print(answer)


solution()

- 비슷한 문제로 양팔저울이 있다

- 배열로 풀긴 했지만 이런 유형은 해시셋 딸깍 하는 게 더 쉽다

문제 푼 순서

No.	문제	날짜
1	A	2026-10-02