중간에서 만나기 테크닉 - 저장하고 검사하는 것이 아니라 검사를 먼저하고 저장하기

5624번: 좋은 수 (acmicpc.net)

 

 

정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우,

 

그러한 수의 개수를 구하는 문제

 

"세 수"는 중복해서 선택해도 좋다

 

예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다

 

n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다

 

대충 이런 느낌

 

for i in range(n):
    
    a = A[i]
    
    for j in range(i):
        
        for k in range(i):
            
            for w in range(i):
                
                b = A[j] + A[k] + A[w]
                
                if b == a:
                    
                    count += 1
                    break

 

 

다음으로는... 이미 이 문제를 해결하기 위해 비슷한 테크닉을 익힌적이 있다

 

https://deepdata.tistory.com/772

[Java]HashMap 응용력 키우기2 -두 수의 합과 세 수의 합 그리고 네 수의 합-

 

만약에, 현재 위치 i 이전의 (j,k)에 대하여 A[j] + A[k]를 미리 hash나 배열에 저장해둔다면..

 

A[i] = A[j] + A[k] + A[w]이므로, A[i] - A[w] = A[j] + A[k]니까, A[i] - A[w]가 저장된 배열에 존재하는지 확인하면 된다

 

그래서 다음과 같이 모든 i = 0,1,2,..,n에 대하여...

 

j = 0,1,2,..i-1, k = 0,1,2,..,i-1에 대해 A[j] + A[k]를 미리 저장해두고

 

w = 0,1,2,...,i-1에 대하여 A[i] - A[w]가 존재하는지 체크하면.. $O(N^{3})$에 가능하다.

 

for i in range(n):
    
    a = A[i]
    
    for j in range(i):
        
        for k in range(i):
            
            P[A[j] + A[k]] = 1
    
    for w in range(i):
        
        if P[a - A[w]] == 1:
            
            count += 1
            break

 

 

n이 최대 5000이라 $O(N^{3})$도 느리다..

 

만약 배열 P에 A[k] + A[w]의 값이 저장되어 있다면, 위치 i 이전의 j에 대하여 A[i] - A[j]가 존재하는지만 체크해도 충분하다

 

왜냐하면 A[i] = A[j] + A[k] + A[w], j,k,w < i이므로 A[i] - A[j] = A[k] + A[w]이기 때문이다.

 

이것을 $O(N^{2})$에 할 수 있는 엄청난? 테크닉이 있는데...

 

저장을 먼저하고 검사를 하는게 아니라, 검사를 먼저 하고 저장을 하는 것이다

 

모든 i = 0,1,2...,n-1에 대하여

 

j = 0,1,2,..,i-1에 대해 P[A[i] - A[j]] = 1이면, A[i]는 조건을 만족하는 수이므로 counting (검사 먼저)

 

이 반복문이 끝나면 k = 0,1,2,..i에 대하여 P[A[i] + A[k]] = 1로 표시 (검사하고 저장하기)

 

이렇게 하면 

 

i = 0에서 i = 0보다 앞에 있는 수는 없으므로 검사할 수는 없고 P에 A[0] + A[0]가 저장

 

i = 1에서 i = 1보다 앞에 있는 수는 A[0]이니 가능한 경우는 A[0] + A[0] + A[0]이고...

 

현재 P에는 A[0] + A[0]만 저장되어 있으며, A[1] - A[0]가 A[0] + A[0]와 같은지 보면 된다.

 

그리고 P에 A[1] + A[0], A[1] + A[1]이 저장

 

i = 2에서 i = 2보다 앞에 있는 수는 A[1], A[0]이니 가능한 경우는

 

A[0] + A[0] + A[0] 

 

A[0] + A[0] + A[1]

 

A[0] + A[1] + A[1]

 

A[1] + A[1] + A[1]

 

i = 2보다 작은 j = 0,1에 대하여.. A[2] - A[0], A[2] - A[1]이

 

A[0]+A[0], A[0] + A[1], A[1] + A[1]중 하나와 같은지만 보면 된다.(검사 먼저)

 

실제로 P에는 이 3개의 수만 저장되어 있고

 

검사가 끝나면 A[0] + A[2], A[1] + A[2], A[2] + A[2]가 저장(검사하고 저장하기)

 

.....

 

이런식으로 하면 정말 놀랍게도 $O(N^{2})$에 가능해진다...

 

저장을 먼저하고 검사하는게 아니라..

 

일단 검사를 먼저하고 저장하기!

 

for i in range(n):
    
    a = A[i]
    
    for j in range(i):
        
        if P[a - A[j]] == 1:
            
            count += 1
            break
    
    for j in range(i+1):
        
        P[a + A[j]] = 1

 

 

여기서 실수한게 있는데

 

배열 P의 범위는 A가 -10만에서 10만까지이고 두 수의 합이 저장되어야 하니까 20만이면 충분?

 

그러면 안돼

 

두 수의 합이 저장되어야 하니까 -20만에서 20만까지 가능하고,

 

배열의 인덱스는 음수가 없으니까 40만까지 저장할 수 있어야한다...

 

#현재 위치 i 이전의 세 수의 합이 현재 위치 i번째 수와 같은 경우를 세는 방법
n = int(input())

A = list(map(int,input().split()))

count = 0

#A가 -10만~10만이고, 두 수의 합이 저장된다
#-20만~20만을 저장할려면 크기가 40만이어야 한다
P = [0]*(4*10**5+1)

#A[i] = A[j] + A[k] + A[w], j,k,w < i인 i의 개수를 센다
#A[i] - A[j] = A[k] + A[w]이므로, 
#k,w < i인 A[k] + A[w]의 값이 저장된 배열이 있다면, 
#i = 0,1,2..,n-1, j = 0,1,2,..,i-1에 대해 A[i] - A[j]가 배열에 존재하는지 체크하면 된다

#이것을 O(N^2)에 하는 놀라운 테크닉
#검사를 먼저하고 저장하기
for i in range(n):
    
    a = A[i]
    
    #먼저 P에 A[i] - A[j]가 존재하면, counting
    for j in range(i):
        
        if P[a - A[j]] == 1:
            
            count += 1
            break
    
    #그리고 j = 0,1,2,..,i에 대하여 A[i] + A[j]를 표시
    for j in range(i+1):

        P[a+A[j]] = 1
    
    #이렇게 하면 다음에는 i+1에서 검사하게 될거고
    #배열 P에는 i+1 이전의 j = 0,1,2,.,i, k= 0,1,2..,i에 대하여 A[j] + A[k]의 값이 저장되어 있다

print(count)

 

 

 

여기서 뭐 A[i] + A[j] = -20만이 될 수 있어서 a+ A[j]가 음수가 될 수 있는데.... 그래서 +20만을 해서 옮겨야 하는거 아니냐

 

그러는데 굳이 안해도 된다

 

A[i] + A[j]가 0~20만은 0~20만에 표시 될거고

 

A[i] + A[j]가 -20만~0은 20만~40만에 표시될거니까