백준 1253번 좋다 (c++)

1253번: 좋다

문제분석

N개의 배열 중, 어떤 숫자를 n이라 할 때, 다른 수 '두' 개의 합으로 나타낼 수 있는 '좋은' 수의 개수를 찾는 문제이다.

문제를 보면 두 수의 합이 n과 같은 경우의 수만 찾으면 된다고 생각하지만... 중요한 포인트는 2개이다.

1. 배열의 원소는 중복될 수 있다. 그리고 수의 위치가 다르면 값이 같아도 다른 수이다.

2. '두' 개의 합으로 목표의 숫자를 만들어야 한다.

---

1. 배열의 원소 중복

예를 들어서, [1 2 3 3 3 4 5]의 배열이 있다고 가정하자.

첫번째 3이 좋은수인지 판단하고자 할 때, 이에 대한 합을 찾을 때 3을 포인터 중 하나로 확인할 수 있다.

또 3은 1과 2로 좋은 수이며, 나머지 2개의 3도 좋은 수에 포함되기에, 위 배열에서의 좋은 수는 총 4개이다. (3, 3, 3, 5)

 

2. '두'  개의 합

목표로 하는 숫자를 두 개의 합으로, '2'가 포인트이다. 두 개의 요소만을 비교해서 원하는 숫자에 도달하면 되기에 '투 포인터'를 사용한다면 쉽게 풀 수 있는 문제이다. 투 포인터에 관련된 설명 글은 아래에 링크를 걸어놓겠다.

[Algorithm] 투 포인터(two pointer) 완.전.정.복

---

문제풀이

투 포인터를 이용할 떄, start point와 end point를 어디에 두느냐가 중요하다. 현재는 어떤 수를 기준으로 할 떄, 다른 두 수의 합을 찾아야 하기에, 정렬된 상태에서 가장 큰 수(end)와 가장 작은 수(start)에서 시작하는 것이 반복문을 탈출하기 가장 빠르다. 

또 두 수의 합이 되는 기준 수는 start point와 end point의 요소가 될 수 없기에, 피해가도록 해야 한다.

 

문제를 보고 써야할 알고리즘이 뭔지, 문제에서 조심해야할 부분이 뭔지만 잘 찾는다면 풀기 쉬울것이다!

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, num = 0;
	cin >> N;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}
	sort(vec.begin(), vec.end());

	for (int i = 0; i < N; i++) {
		int point = vec[i]; 
        // '좋다'가 될 수 있는 수인지 판단하고자 하는 기준
        
		int startp = 0, endp = N - 1;
		while (startp < endp) {
			if (startp == i) {
				startp++;
				continue;
			}
			else if (endp == i) {
				endp--;
				continue;
			}
            // 관문1 : 투 포인터가 현재 가리키는 i와 같은가?
            // 같다면, 다음 수를 가리키도록 한다.

			if (vec[startp] + vec[endp] > point) {
				endp--;
			}
			else if (vec[startp] + vec[endp] < point) {
				startp++;
			}
			else {
				num++;
				break;
			}
            // 관문2 : 투 포인터가 가리키는 부분의 합이 point와 같은가?
            // 같을 경우 num++, 다를경우 포인터가 무엇인지에 따라 이동
		}
	}

	cout << num;

	return 0;
}

코드 리뷰는 언제나 환영입니다!