[백준 BOJ] 3273번 두 수의 합 (C++/cpp)

문제 설명

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

3273번: 두 수의 합

 

접근 방법 - 정렬을 응용한 두 포인터 문제

백준의 3273번 문제는 정렬과 함께 해결해야 하는 두 포인터 알고리즘 문제이다.

해당 문제는, 주어진 숫자들 중 2개의 합이 특정 입력값과 같은 경우가 몇 개인지를 구하여 출력해야 하는 문제이다.

이 문제는 두 포인터 알고리즘을 이용하여 해결해야 하는데, 이와 비슷한 유형의 문제에 대해 이전에 업로드한 ps글이 있다.

링크는 아래에 기재하니, 이 알고리즘을 처음 접한다면 아래의 링크도 함께 참고해보길 바란다.

https://smary-it.tistory.com/246

[백준 BOJ] 2018번 수들의 합 5 (C++/cpp)

이 문제에서 두 포인터 알고리즘을 적용하기 위해선 정렬을 해야 하기 때문에 이 점을 꼭 주의하자.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 덧셈 연산에 사용할 숫자들을 저장할 배열(arr)을 전역 변수로 선언해둔다.

 

2) 숫자의 개수(n)를 입력받고, n의 크기에 따라 arr의 값들을 입력받는다.

 

3) 원하는 합 결과(sum)를 입력받는다.

 

4) 숫자 크기에 따라 숫자 교체를 해야 하기 때문에, 함수를 통해 arr 배열에 대한 정렬을 수행한다.

 

5) 가짓수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

6) 정렬 완료된 arr에 대하여, 양 옆으로 숫자를 적절히 선택하며 아래의 연산을 취한다.

(그렇기 때문에, 초반에는 가장 작은 숫자(j)와 가장 큰 숫자(i)가 탐색될 것이다.)

- 만일 두 숫자의 합이 sum보다 크다면, 큰 숫자(i)를 더 작은 숫자로 고를 수 있도록 한다.

- 만일 두 숫자의 합이 sum보다 작다면, 작은 숫자(j)를 더 큰 숫자로 고를 수 있도록 한다.

- 만일 두 숫자의 합이 sum과 같다면, 가짓수에 해당하기 때문에 cnt에 1을 더하도록 한다.

 

7) 연산이 완료되었다면, 최종적으로 저장된 cnt를 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 3273번 코드
int arr[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, sum;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> sum;
	sort(arr, arr + n);

	int cnt = 0;
	int i, j = 0;
	for (i = n - 1; i > j; i--) {
		for (j = 0; j < i; j++) {
			if (arr[i] + arr[j] > sum) { break; }
			if (arr[i] + arr[j] == sum) {
				cnt++;
			}
		}
	}

	cout << cnt << endl;
}

 

제출 결과

(2022.08.06 백준 3273번 문제 제출 결과)