[백준]5624 좋은수 #시뮬레이션#dp

1. 풀이

(1) i+j+k=x를 i+j=x-k로 바꿔서 생각한다. (i번째수 + j번째수 = x번째수 - k번째수)

(2) x가 가능한지 확인: k가 0번째부터 x-1번째까지 한번돌면서 (x번째-k번째)가 가능(방문되었는지)한지 확인

(3) x까지 추가되서 만들수 있는 숫자 최신화 : j가 0번째부터 x번째까지 돌면서 새로운숫자 (x번째+j번째)를 방문

* Ai의 범위는 -100000~100000이므로 x-k의 범위는 -200000~200000. 따라서 이를 리스트 인덱스로 만들어주려면 0~400000아 되므로 isPossible 리스트는 400001로 초기화

(4) (2),(3)의 과정을 N번반복. O(N^2)

​

2. 소스코드

N=int(input())
L=list(map(int,input().split()))
isPossible=[0 for i in range(400001)]

ans=0
#숫자 하나씩 확인
for x in range(N):
    #있는지 확인
    for k in range(x):
        if isPossible[L[x]-L[k]+200000]:
            ans+=1
            break
    #숫자추가
    for j in range(x+1):
        isPossible[L[x]+L[j]+200000]=1
print(ans)