[백준] 좋다(1253)

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

어떤 목표값이 서로 다른 두 수의 합으로 나타낼 수 있다면 해당 경우를 카운트 하는 문제이다.

문제의 핵심은 두 수가 서로 달라야 한다. 다시 말해 목표값인 자기 자신을 포함하면 안된다는 말이다.

따라서 아래와 같이 2가지 케이스에 대해 예외 처리를 진행해주어야 한다.

e.g. 1) A = [1, 2, 3], start_idx = 0, end_idx = 2, k = 0일 때
start_idx와 k가 서로 같은 1을 가리키므로 A[k]가 두 수의 후보로 쓰이는 것을 피하기 위해 start_idx를 증가시킴

e.g. 2) A = [1, 2, 3], start_idx = 0, end_idx = 2, k = 2일 때
end_idx와 k가 서로 같은 3을 가리키므로 A[k]가 두 수의 후보로 쓰이는 것을 피하기 위해 end_idx를 감소시킴

또한 N의 최댓값이 2,000이고 시간제한이 2초이므로 $O(n^2)$까지 허용된다.

따라서 문제풀이 방법은 아래와 같다.

1. 입력값 오름차순 정렬

2. 목표값 k를 N까지 반복하면서

3. 시작 인덱스와 마지막 인덱스가 서로 동일한 위치에 도달할때까지

   3-1-1. 어떤 두 수의 합이 목표값과 같은 경우
   => 시작, 마지막 인덱스 모두 목표값 인덱스가 아닌 경우 정답 카운트
   => 목표값 인덱스인 k를 다음 번째 순서로 증가

   3-1-2. 시작 또는 마지막 인덱스가 목표값 인덱스인 경우
   => 시작인덱스 증가 또는 마지막 인덱스 감소

   3-2-1. 어떤 두 수의 합이 목표값보다 작은 경우
   => 시작 인덱스를 증가하여 합을 늘림

   3-2-2. 어떤 두 수의 합이 목표값보다 큰 경우
   => 마지막 인덱스를 감소시켜 합을 줄임

Python

import sys
input = sys.stdin.readline

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

# 배열 오름차순 정렬
arr.sort()

count = 0

# 배열의 첫 번째 원소부터 N 번째 원소까지 반복
# k는 첫 번째 원소 ~ N 번째 원소를 순회하면서 가지는 목표값

# e.g. 1 + 2 = 3의 예시
# arr[i] == 1
# arr[j] == 2
# arr[k] == 3
for k in range(N):
    i = 0 # 시작 인덱스
    j = N -1 # 마지막 인덱스

    # 모든 검사가 끝날 때 까지
    while i < j:
        # 어떤 두 수의 합이 목표값과 같은 경우
        if arr[i] + arr[j] == arr[k]:
            # i와 j 모두 목표값이 아닌 경우
            if i != k and j != k:
                # 정답 카운트
                count += 1
                break
            
            # i 또는 j가 목표값인 경우
            elif i == k:
                i += 1
            elif j == k:
                j -= 1

        # 어떤 수의 합이 목표값보다 작은 경우
        elif arr[i] + arr[j] < arr[k]:
            # 가장 최근에 설정한 가장 작은 자연수를 고려하지 않음
            i += 1
        
        else:
            # 수의 범위 증가
            j -= 1

print(count)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P_1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);

        int count = 0;

        for (int k = 0; k < N; k++) {
            int start_idx = 0;
            int end_idx = N - 1;

            while (start_idx < end_idx) {
                if (A[start_idx] + A[end_idx] == A[k]) {
                    // 가리키는 두 수가 서로 다른 경우
                    if (start_idx != k && end_idx != k) {
                        count++;
                        break;
                    } else if (start_idx == k) { // e.g.1 케이스
                        start_idx++;
                    } else { // e.g.2 케이스
                        end_idx--;
                    }
                } else if (A[start_idx] + A[end_idx] < A[k]) {
                    start_idx++;
                } else {
                    end_idx--;
                }
            }
        }

        System.out.println(count);
    }
}