SWEA-3752-가능한 시험 점수

풀이

문제조건 해석

가능한 점수의 경우의 수 찾는 문제다. 특별한 테크닉을 사용해야 한다.

알고리즘

BFS와 메모이제이션 기법으로 가까스로 통과하긴 했다.

하지만, 이 문제는 완전탐색 또는 DP 문제가 아니다.

최대 점수 범위 내 모든 점수에 대해 가능한지 여부를 담는 배열을 선언하고

모든 문제를 순회하며 가능한 점수에 대해 문제 점수를 더한다.

기존 가능한 점수 + 더한 문제 점수 는 새롭게 가능한 점수가 된다.

코드

for t in range(1, int(input())+1):
    n = int(input())
    scores = [int(x) for x in input().split()]
    dp = [False for _ in range(sum(scores)+1)]
    # dp[i] : i가 받을 수 있는 점수이면 True
    dp[0] = True # 0은 항상 가능한 점수
    for score in scores:
        for i in range(len(dp)-1, -1, -1): 
        # 역순으로 순회해야 업데이트된 dp값에 접근하지 않음
            if dp[i]: # i는 더할 수 있는 점수
                dp[i+score] = True
    print('#{}'.format(t), sum(dp))

배운점

경우의 수 문제에서 이 문제와 같은 테크닉을 사용하는 유형은?

• 중복을 무시해야 한다.
• 경우의 수의 범위가 한정적이어야 한다(이 문제에서는 100*100)
• $O(N배점N)$