[골드 4] 백준 1253 - 좋다 (파이썬)

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

풀이

핵심 아이디어는 투포인터 기법을 이용하여 어떤 수가 두 수의 합으로 표현될 수 있는지를 판별하는 것이다.

즉, N개의 수가 주어졌을때, 그 수들 중 어떤 수 하나가 나머지 두수의 합으로 표현될 수 있는 경우를 찾고, 그러한 수의 개수를 구하는 문제이다.

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

A를 정렬하면 투 포인터를 사용할 수 있는 기반이 마련된다.

for j in range(N):
    if j == i:
        continue
    target = A[i] - A[j]

A[i]에서 A[j]를 빼서 나머지 한 수 target이 A 배열 안에 존재하는지 확인한다.

k = N - 1
if k == i:
    k -= 1

투포인트의 코드이다. (오른쪽 포인터 k 이동), k는 오른쪽 포인터로, A[k] == target 인지를 보면서 줄여 나간다.

k == i 인 경우는 제외해야 하므로 조정해준다.

while j < k and A[k] > target:
    k -= 1
    if k == i:
        k -= 1

A[k] > target 이면 더 작은 수를 찾아야 하므로 k -= 1을 진행한다.

또한 k == i 이면 자기 자신이므로 스킵한다.

if j != k and A[k] == target:
    found = True
    break

j와 k가 다르고, A[k] == target이면, A[i] = A[j] + A[k] 를 만족하는 것이므로 좋은 수이다.

개선 사항

이 코드는 투 포인터를 직접 활용하기보단 이분 탐색과 섞인 구조이다. 더 직관적인 투 포인터 방식으로 전체 배열을 순회하며 두 수의 합을 찾아가는 것도 가능 할 것 같다.

코드

# 백준 1253 - 좋다
# 분류 : 투포인터

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

A.sort()

count = 0
for i in range(N) :
    k = N - 1
    if k == i :
        k -= 1

    found = False
    for j in range(N) :
        if j == i :
            continue

        target = A[i] - A[j]

        while j < k and A[k] > target :
            k -= 1
            if k == i :
                k -= 1

        if j != k and A[k] == target :
            found = True
            break
    
    if found :
        count += 1

print(count)