[알고리즘] C++ 백준 20366 같이 눈사람 만들래?

백준 20366

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

20366번: 같이 눈사람 만들래?

풀이 전 나의 생각

N개의 눈덩이가 주어졌을 때 2개의 눈덩이로 만든

눈사람 2개의 지름 차이가 최소가 되는 경우를 구해야 한다. 

 

조건

- N (4 ≤ N ≤ 600)

- Hi (1 ≤ Hi ≤ 109)

- i (1 ≤ i ≤ N)

 

과정

문제를 푸는 방법은 두 가지가 있다.

 

첫 번째로 2중 for문을 이용하여 푸는 방법이 있다.

하지만 여기서 주의할 점은 눈사람을 만들 수 있는 모든 경우를

구했다고 한들 중복되는 경우가 생긴다는 것이다.

 

예를 들어 미리 구해놓은 눈사람을 비교한다고 가정하자.

눈덩이가 3 5 2 5 9가 있을 때
인덱스의 0번, 1번을 더한 눈사람 3 + 5 = 8과 
인덱스의 1번, 2번을 더한 눈사람 5 + 2 = 7을 

비교한다면 인덱스 1번이 중복되서 답의 오류가 날 것이다.

 

따라서 for문을 통한 풀이는 눈사람을 만들 수 있는 모든 경우를 구하면서
눈사람을 만들 때 사용했던 눈덩이 인덱스의 정보를 추가해야 한다.

 

두 번째로 투 포인터를 이용하여 푸는 방법이 있는데
문제 풀이는 투 포인터로 진행했다.

 

이 문제는 결국 최소값을 구해야 하기 때문에 모든 눈덩이를 효율적으로
탐색하는 방법이 필요하다.

이를 위한 과정은 다음과 같다.

1. 눈덩이를 정렬 해준다.

2. 최소 3의 공간을 두고 2중 for문을 진행하며 한 명의 눈사람을 만들어준다.

-> 최소 3의 공간이 필요한 이유는 엘사와 안나의 눈사람을 만들기 위한 최소 공간 (0 ~ 3)
3. 기존에 눈사람을 만들었던 눈덩이 사이에 투 포인터를 적용하여 나머지 한 명의 눈사람을 만들어준다.
4. 눈사람의 지름 차이를 구한다.

 

예를 들어 3 5 2 5 9의 눈덩이를 정렬 한 2 3 5 5 9 가 있다고 할 때

 

for문에서 눈덩이가 인덱스 0번, 4번이 선택됐다고 하면
그 사이의 인덱스 1, 2, 3번에 투 포인터를 적용해야 한다.

(0번 + 4번 눈사람) - (시작 포인터(0번 + 1) + 끝 포인터(4번 - 1) 눈사람) 의 결과가 
0보다 크다면 바깥쪽 눈사람 값이 크기 때문에 안쪽 눈사람의 시작 포인터를 증가 시켜주고
반대의 상황이면 끝 포인터를 감소 시켜준다.

만약 정렬을 해주지 않았다면 포인터를 감소하거나 증가하는 부분에 있어서

올바른 의도대로 조건이 해결되지 않는 문제가 발생한다.

 

이런 점을 유의하면서 문제를 풀면 답을 구할 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int snow[601];

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

	int N, ans = INT_MAX;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> snow[i];
	}

	// 투 포인터의 올바른 탐색을 위해서 눈덩이 정렬
	sort(snow, snow + N);

	// 엘사와 안나의 눈사람을 만들기 위해 최소 공간 3을 띄어준다.
	for (int i = 0; i < N - 3; ++i)
	{
		for (int j = i + 3; j < N; ++j)
		{	
			int start = i + 1, end = j - 1, elsa = snow[i] + snow[j];

			while (start < end)
			{
				int anna = snow[start] + snow[end];
				int res = elsa - anna;
				ans = min(ans, abs(res));

				//현재 비교한 눈사람 지름 차이가 0보다 크다면 시작 포인터 증가
				if (res > 0) start++;
				//현재 비교한 눈사람 지름 차이가 0보다 작다면 끝 포인터 감소
				else if (res < 0) end--;
				// 0이라면 무조건 최솟값이기 때문에 0출력 후 종료
				else
				{
					cout << "0";
					return 0;
				}
			}
		}
	}

	cout << ans;
}