[백준/Python] 2295번: 세 수의 합

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

2295번: 세 수의 합

---

---

문제 분석

중복이 가능한 세 수를 골라 집합에 있는 수를 만들면 된다.

N이 1000까지 가능하기 때문에 삼중 for문을 사용하여 세 수를 각각 골라 계산한다면

시간복잡도가 O(N**3)이 될 것이다.

큰 시간복잡도를 가지므로 다른 방법을 생각해보자.

 

우선 탐색을 위한 하나의 수(k번째 수)를 정한다.

이 수는 세가지 수의 합을 의미하는 수이다.

 

그 후 조합이 되는 세가지 수를 정해야 하는데

이 때, 사용할 수 있는 방법은 하나의 수를 정한 뒤 미리 정한 수에 뺀 값을 확인하는 방법이다.

 

즉, (k번째 수) - (z번째 수) = (x번째 수) + (y번째 수)가 되는 것이다.

이 방법을 사용하면 두 번의 반복문만으로 문제를 해결할 수 있다.

 

x번째 수와 y번째 수를 더한 값을 미리 입력받은 리스트에서 구해놓은 뒤

반복할 때마다 리스트에서 있는지 체크하면 된다.

 

코드1

set의 in을 사용

import sys

input = sys.stdin.readline


def solution():
    # 가장 큰 수부터 두 수의 차이를 계산해서 남은 두 수의 합을 만들 수 있으면
    # 세 수의 합이 존재하는 것
    # (x + y) = k - z
    for i in range(N - 1, -1, -1):
        for j in range(i, -1, -1):
            num = arr[i] - arr[j]

            if num in sumL:
                return arr[i]


N = int(input())
arr = [int(input()) for _ in range(N)]
sumL = set()

arr.sort()

# 두 수의 합 리스트 생성
for i in range(N):
    for j in range(i, N):
        sumL.add(arr[i] + arr[j])

print(solution())

 

---

코드2

이분 탐색을 사용 (시간이 더 느리다..?)

import sys

input = sys.stdin.readline


def solution():
    # 가장 큰 수부터 두 수의 차이를 계산해서 남은 두 수의 합을 만들 수 있으면
    # 세 수의 합이 존재하는 것
    # (x + y) = k - z
    for i in range(N - 1, -1, -1):
        for j in range(i, -1, -1):
            num = arr[i] - arr[j]

            if bs(num):
                return arr[i]


# 이분 탐색
def bs(num):
    l, r = 0, len(sumL)

    while l <= r:
        m = (l + r) // 2

        if num == sumL[m]:
            return True
        elif num > sumL[m]:
            l = m + 1
        elif num < sumL[m]:
            r = m - 1

    return False


N = int(input())
arr = [int(input()) for _ in range(N)]
sumL = set()

arr.sort()

# 두 수의 합 리스트 생성
for i in range(N):
    for j in range(i, N):
        sumL.add(arr[i] + arr[j])

sumL = sorted(list(sumL))

print(solution())

 

---

코드3

itertools의 combinations_with_replacement를 이용

이 함수는 배열과 반복 횟수를 지정해서 중복이 가능한 조합을 구하는 함수이다.

 

가장 빠른 방법

import sys
from itertools import combinations_with_replacement

input = sys.stdin.readline


def solution():
    # 가장 큰 수부터 두 수의 차이를 계산해서 남은 두 수의 합을 만들 수 있으면
    # 세 수의 합이 존재하는 것
    # (x + y) = k - z
    for i in range(N - 1, -1, -1):
        for j in range(i, -1, -1):
            num = arr[i] - arr[j]

            if num in sumL:
                return arr[i]


N = int(input())
arr = [int(input()) for _ in range(N)]

arr.sort()
sumL = {x + y for x, y in combinations_with_replacement(arr, 2)}

print(solution())