[Python] 2295번 세 수의 합

https://www.acmicpc.net/problem/2295

2295번: 세 수의 합

---

 

23/12/28

 

 

중간에서 만나기(MITM)으로 안 풀어도 집합으로 쉽게 풀 수 있는 문제이다.

 

나는 중간에서 만나기 알고리즘 연습을 위해 그 방법으로 문제를 해결했다.

---

 

첫번째 문제 접근 방식:

 

 

MITM으로 해결했다.

 

세 수의 합이 최대가 되도록 하려는 것이 우리의 목적이고, 그 세 수의 합 또한 기존 배열에 존재해야 한다.

 

나는 두 개로 분할했는데, 하나는 $x$번째 수와 $y$번째 수를 더한 합 배열, 그리고 $z$번째 수에서 $k$번째 수를 뺀 차 배열을 생각했다.

 

편의 상 전자를 $xy$배열, 후자를 $zk$배열이라고 하자.

 

$xy$배열이 정렬되어 있다고 하면, 우리는 $zk$배열의 원소에 음의 부호를 취해준 것, 즉, $k$번째 수에서 $z$번째 수를 뺀 원소 하나 당 조건을 만족시키는 $xy$배열 하나를 이분 탐색을 통해 찾아낼 수 있을 것이다.

 

즉, $U[x] + U[y] = U[k] - U[z]$를 만족시키는 $xy$배열의 원소 하나를 찾아낼 수 있다.

 

따라서 $\mathcal{O}(N^2\mathrm{log}N)$의 시간 복잡도로 문제를 해결할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2295번 세 수의 합
# 분할 정복
'''
접근 방법:
밋 인더 미들
'''
import sys
input = sys.stdin.readline

def bisect(num, li):
    start, end = 0, len(li)-1
    while start <= end:
        mid = (start+end)//2
        if li[mid] == num:
            return mid
        if li[mid] > num:
            end = mid-1
        else:
            start = mid+1
    if li[start] == num:
        return start
    return None

N = int(input())
U = list(int(input()) for _ in range(N))
num_li1 = [0 for _ in range(N*N)]
num_li2 = [0 for _ in range(N*N)]
for i in range(N):
    for j in range(N):
        num_li1[i*N+j] = U[i] + U[j]
        num_li2[i*N+j] = U[i] - U[j]
num_li1.sort()
max_val = 0
for z in range(N):
    for k in range(N):
        num = -num_li2[z*N+k]
        a = bisect(num, num_li1)
        if a != None and U[k] > max_val:
            max_val = U[k]
print(max_val)

---

 

두번째 문제 접근 방식:

 

 

$xy$배열을 만든다는 것 자체는 같지만, 정확히 말하면 배열이 아니라 집합으로 구현함으로써 시간을 더 줄일 수 있다.

 

있는지 없는지 확인하는 것은 상수의 시간이 걸리기 때문에, $\mathcal{O}(N^2)$의 시간 복잡도로 해결할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2295번 세 수의 합
# 이분 탐색
'''
접근 방법:
이분 탐색 + 집합
'''
import sys
input = sys.stdin.readline

N = int(input())
U = sorted(int(input()) for _ in range(N))
num_set = set(U)
num_li1 = set(i+j for i in U for j in U)
max_val = 0
for z in range(N):
    for k in range(z, N):
        if (U[k] - U[z]) in num_li1 and max_val < U[k]:
            max_val = U[k]
print(max_val)