문제 접근
점수의 배점이 주어지기 때문에 각각의 배점을 선택하거나, 하지 않거나로 풀 수 있다. 따라서 처음에는 dfs로 문제를 풀고자했다. 하지만 result에 계속해서 많은 값이 들어가다보니 아무래도 메모리 오버플로우가 발생하게 된다. 따라서 하나의 문제를 풀거나, 풀지 않거나를 확인한 후에 중복인 점수는 set을 통해 제거해주도록 했다.
이렇게 하니 메모리가 초과되지 않아 pass할 수 있었다.
문제 풀이
알고리즘 이해하기
하나의 배점을 선택하거나, 하지 않거나이다. 이는 결국 리스트에 받을 수 있는 점수들을 넣고 하나의 문제에 대해 그 문제의 배점을 리스트에 존재하는 모든 값에 더하고 다시 리스트에 넣어주면 된다고 생각한다.
즉 result와 temp라는 리스트에 초기값으로 0이 들어있다.
예제 1번의 입력이 2 3 5이므로 이를 예로들어 설명하겠다.
처음에 0이 들어있는 result를 확인한다.
2를 0과 더하고 temp에 2를 append한다.
result에 temp를 set을 통해 중복을 제거해주고 copy한다.
이제 result에는 0과 2가 들어있다.
배점 3점을 보자.
0+3 = 3, 2+3 = 5을 temp에 넣는다.
temp를 set으로 중복제거하고 copy한다.
이제 result에는 0, 2, 3, 5가 들어있다.
배점 5점을 보자.
0+5 = 5, 2+5 = 7, 3+5 = 8, 5+5 = 10를 temp에 넣는다.
temp를 set으로 중복제거하고 copy하면
result에는 0, 2, 3, 5, 7, 8, 10으로 총 7개이다.
따라서 답이 7이 된다.
구현하기
이를 2중 for문을 사용하여 구현할 수 있었다.
N = int(input())
score = list(map(int, input().split()))
result = [0]
temp = [0]
for i in range(N):
for j, val in enumerate(result):
temp.append(result[j]+score[i]) # 배점 각각 더하고 temp에 append
result = list(set(temp)) # 중복제거하고 copy제출 코드
T = int(input())
for test_case in range(1, T + 1):
N = int(input())
score = list(map(int, input().split()))
result = [0]
temp = [0]
for i in range(N):
for j, val in enumerate(result):
temp.append(result[j]+score[i])
result = list(set(temp))
print(f'#{test_case} {len(result)}')