[G3] 백준 20366번 같이 눈사람 만들래? C++ 투 포인터, 정렬

리뷰

 

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

투 포인터 내부의 투 포인터를 수행하는 문제

 

 

전역 변수

1. N : 배열의 최대 크기를 정의할 상수 변수
2. arr : 눈덩이의 지름을 저장할 배열
3. n : 눈덩이의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 눈덩이 지름을 입력 받아 배열 arr을 초기화한다.
2. sort함수를 통해 arr배열을 오름차순으로 정렬한다.
3. 변수 mn을 20억 이상의 값으로 초기화 한다.
4. 0~n-4인덱스를 순회하는 변수 i를 사용하는 for문을 개행하고, mn이 0일 경우 break를 처리한다.
5. i+3~n-1인덱스를 순회하는 변수 j를 사용하는 for문을 개행하고, mn이 0일 경우 break를 처리한다.
6. 변수 sm1에 arr[i]+arr[j]를 값으로 하는 눈사람의 크기를 저장한다.
7. 변수 l을 i+1, r을 j-1로 초기화한다.
8. l이 r보다 작을 경우를 조건으로 하는 while루프를 수행한다.
9. 변수 sm2에 arr[l]+arr[r]을 값으로 하는 눈사람의 크기를 저장한다.
10. mn과 sm1-sm2의 절대값을 비교하여 더 작은 값을 mn에 저장한다.
11. 만약 sm1이 sm2보다 작을 경우 r을 감소, sm1이 sm2보다 클 경우 l을 증가, 둘이 동일하다면 break처리한다.
12. 모든 탐색을 마친 후 mn에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. N의 최대 범위가 600이므로, O(N^3)의 시간복잡도도 충분히 통과한다.
2. H의 최대 범위가 10억이므로, mn의 최소값은 20억 이상으로 설정하는게 안전하다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 600;
int arr[N];
int n;

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

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

	int mn = 2e9;
	for (int i = 0; i < n - 3; ++i) {
		if (mn == 0) break;

		for (int j = i + 3; j < n; ++j) {
			if (mn == 0) break;
			int sm1 = arr[i] + arr[j];
			int l = i + 1, r = j - 1;

			while (l < r) {
				int sm2 = arr[l] + arr[r];
				mn = min(mn, abs(sm1 - sm2));

				if (sm1 < sm2) --r;
				else if (sm1 > sm2) ++l;
				else break;
			}
		}
	}
	cout << mn;
}