[백준 골드 4] 1253번: 좋다

문제

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

1253번: 좋다

 

 

풀이

• N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 "좋다"라고 한다.
• 주어진 N개의 수 중 좋은 수의 개수를 출력해야 한다.
• 같은 값의 수가 주어질 수도 있지만 서로 다른 수로 취급한다.
• N은 1에서 2000 사이이고, 주어지는 수는 |Ai| ≤ 1,000,000,000 의 정수이다.

 

투포인터를 사용해 N개의 수를 탐색하는 방법으로 풀었다. 이때, 수의 범위가 크므로 Long형 배열로 입력받고 정렬하였다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

long numbers[] = new long[N];

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
    numbers[i] = Long.parseLong(st.nextToken());
}

Arrays.sort(numbers);

 

numbers 배열의 모든 수를 좋은 수인지 판별하기 위해 for문을 사용해 배열 전체를 탐색하였다. 첫번째 인덱스와 마지막 인덱스를 포인터로 사용하고, 포인터가 가리키는 값의 합과 타깃으로 한 수가 같은지 판별하는 while문을 만들었다. while문의 조건은 포인터가 만나게 되는 경우로 정의하였다.

for (int i = 0; i < N; i++) {
    long target = numbers[i];
    int start = 0;
    int end = N - 1;
    long sum = 0;

    while (start < end) {
    	sum = numbers[start] + numbers[end];
        ...
    }
}

 

포인터를 사용해 비교하는 것은 크게 세가지 경우이다. 포인터가 가리키는 값의 합과 타깃을 비교하였을 때, 큰 경우, 작은 경우, 그리고 일치하는 경우이다.

오름차순으로 정렬하였기 때문이 비교한 결과 합보다 타깃이 더 크다면 앞의 인덱스가 +1 만큼 움직여 합의 크기를 키워줘야 한다. 반대로 합보다 타깃이 더 작다면 뒤의 인덱스를 -1 만큼 움직여 합의 크기를 작게 만들어 줘야한다.

if (sum < target) {
    start++;
} else if (sum > target) {
    end--;
}

 

처음에는 다른 투포인터 문제처럼 else에 결과값을 늘리고 break를 하였지만, 생각해보니 포인터가 가리키는 값이 타깃으로 한 숫자인 경우도 제외해야 했다. start나 end 포인터가 타깃에 해당하는 i 인덱스를 가리킨다면, 그래도 통과하면 된다.

else {
    if (start != i && end != i) {
        cnt++;
        break;
    } else if (start == i) {
        start++;
    } else if (end == i) {
        end--;
    }
}

 

 

전체 코드 (Java)

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		long numbers[] = new long[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			numbers[i] = Long.parseLong(st.nextToken());
		}

		Arrays.sort(numbers);

		int cnt = 0;

		for (int i = 0; i < N; i++) {
			long target = numbers[i];
			int start = 0;
			int end = N - 1;
			long sum = 0;

			while (start < end) {
				sum = numbers[start] + numbers[end];

				if (sum < target) {
					start++;
				} else if (sum > target) {
					end--;
				} else {
					if (start != i && end != i) {
						cnt++;
						break;
					} else if (start == i) {
						start++;
					} else if (end == i) {
						end--;
					}
				}
			}
		}

		System.out.println(cnt);

	}

}

 

 

후기

투포인터는 늘 복잡하게 생각하지 말고 주어진 조건을 차근차근 구현하면 되는 것 같다. 어느정도 감을 잡은듯 하다.