[백준][Python] 5624 좋은수

1차시 DFS 시간초과

import sys
input = sys.stdin.readline

def DFS(depth,start,sum_t):
    if depth==3:
        if arr[start]==sum_t:
            return True
        return
    for pre_num in arr[:start]:
        if DFS(depth+1,start,sum_t+pre_num):
            return True

N = int(input())
arr = list(map(int,input().split()))

# 앞에있는 수 3개의 합. DFS(중복가능) depth 3까지.
cnt=0
for i in range(1,N):
    if DFS(0,i,0):
        cnt+=1
print(cnt)

2차시 누적합 메모리초과

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))

sums=[[],[],[]]
# 앞의 모든 수를 더하는 집합 set을 만들어보자.
for i in range(N-1):
    sums[0].append(arr[i])
    for sum_num in sums[0]:
        sums[1].append(sum_num+arr[i])
    for sum_num in sums[1]:
        sums[2].append(sum_num+arr[i])
cnt=0
for i in range(1,N):
    if arr[i] in sums[2]:
        cnt+=1

print(cnt)

3차시 A+B= D-C 로 통과. 3개를 더하려면 N^3이기 때문에 2*N^2로 통과하는 방법이다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
dp = [0]*400003
tmp = 200001

answer = 0
for i in range(N):
    for j in range(i):
        if dp[arr[i] - arr[j]+tmp]==1:
            answer+=1
            break
    for k in range(i+1):
        dp[arr[i]+arr[k]+tmp] = 1
    
print(answer)