[SWEA] Q1247 최적 경로

[SWEA] Q3752 가능한 시험 점수

Question

Language: Python

Difficulty: D4

1495 문제와 유사한 방식으로 풀어줄 수 있다.

input이 아래와 같은 경우

3
2 3 5

각 배점에 대해서 적용하면 아래와 같은 결과를 얻을 수 있다.

	0	1	2	3	4	5	6	7	8	9	10
1	True		True
2	True		True	True		True
3	True		True	True		True		True	True		True

Solution

def solution():
    max_score=sum(scores)

    dp=[[False] * (max_score+1) for _ in range(n)]

    # 첫번째 점수에 대한 경우
    dp[0][0],dp[0][scores[0]]=True,True

    for i in range(1,n):
        score=scores[i]
        for j in range(max_score):
            if dp[i-1][j]:
                #틀리는 경우
                dp[i][j] = True
                #맞는 경우
                dp[i][j+score]=True

    return sum(dp[n-1])

if __name__ == "__main__":
    n=0
    scores=[]

    with open("input.txt","r" ) as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n=int(file.readline())
            scores=list(map(int,file.readline().split()))
            print(f"#{case+1} {solution()}")