[백준 20366][💛3] 같이 눈사람 만들래? (조합, 투포인터)

🚀 난이도

💛 골드 3

🚀 문제

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

🚀 내 풀이

어려웠다.. 결국 다른 분들의 풀이로 공부를 했던 문제였다. 😅

🔥 첫 번째 풀이 (조합)

코드 출처 블로그 https://imnotabear.tistory.com/379

최대 입력 크기가 600 이기 때문에 서로 다른 4 개의 눈 덩이 조합을 뽑는다면 시간 초과가 발생할 것이다.(600 C 4) 우선 2 개의 눈덩이끼리의 조합을 구하여 그 눈덩이들을 묶어 나열한다.(이를 snowman 라고 하겠다.) 눈덩이 2 개로 눈사람 하나를 만드는 것이기 때문에 이 bind 에서 엘사의 눈사람, 안나의 눈사람으로서 2 개를 뽑는다. 즉, 눈덩이 2 개를 뽑아 하나의 원소로서 묶어 나열한 snowman 에서 또 2 개를 뽑아 눈사람 2 개를 조합으로 뽑는 식이다. 여기까지만 생각해보면 N C 2 * N C 2 가 되어 엄청나게 큰 입력 크기가 될 것 같지만..

문제에서 구하고자 하는 것은 엘사 눈사람과 안나 눈사람 “최소 길이 차이”를 구하는 것이기 때문에 눈덩이 2 개를 조합으로 뽑아 묶아 나열한 snowman 를 먼저 정렬을 한 후, 각 원소마다 자신의 바로 뒤에 있는 것을 선택하여 그것과 키 차이를 구하면 된다. 오름차순으로 정렬을 한 상태인데다가 최소 길이 차이를 구하는 것이기에 자신의 뒤에 있는, 즉 자신 보다 키가 큰 눈사람들 중 전부 다 비교할 필요 없이 그냥 바로 뒤에 있는 눈사람을 선택해주면 되는 것이다. 그게 바로 자신보다 키 큰 눈 사람 중에서 자신과 가장 최소로 차이 나는 눈사람이 되는 것이기 때문이다! (‘자신’을 안나 눈사람, ‘안나 눈사람 보다 큰 눈사람들 중에서 가장 최소로 차이 나는 눈사람’을 엘사 눈사람이라고 하자.)따라서 이때의 시간 복잡도는 N C 2 * N C 2 이 아닌 대략 N C 2 가 된다.

다만! 서로 다른 눈덩이를 써야하기 때문에 뽑힌 4 개의 눈덩이는 같은 index 여서는 안된다. 모두 다른 인덱스여야 한다! 두 눈덩이(인덱스)를 뽑아 모아둔 snowman에서 또 2 개를 뽑는 것이다 보니 뽑은 두 눈사람 중 같은 눈덩이가(즉 인덱스가 동일한) 있을 수 있다.

따라서 정렬된 상태에서 현재 안나의 눈사람으로 설정된 눈사람 중 뒤에 위치한 눈사람들 중에서 넷 다 서로 다른 눈덩이라는 전제가 처음으로 성립하는 눈사람을 엘사 눈사람으로 지정한 후 두 눈사람의 키 차이를 구하면 될 것이다. N C 2 의 시간 복잡도 동안 차례로 안나의 눈사람으로 설정한 후 두 눈 사람의 키 차이를 구하여 최소값을 업데이트 해 나가면 된다.

#include <bits/stdc++.h>

using namespace std;

struct Elem { int index1, index2, sum; }; // 이 구조체 하나가 눈사람이나 마찬가지다. index 1,2 로 두 눈덩이 구분(인덱스), sum 은 눈사람 길이가 됨. 
bool cmp(const Elem& a, const Elem& b) {
	return a.sum < b.sum; // 눈사람 키 별로 정렬
}

int main() {
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

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

	// 1️⃣ 두 눈덩이의 조합, 즉 NC2 개의 조합을 구한다. 이를 snowman 에 저장. 즉, 만들 수 있는 눈사람들 나열!
	vector<Elem> snowman;
	for (int i = 0; i < N - 1; ++i)
		for (int j = i + 1; j < N; ++j)
			snowman.push_back({ i, j, snow[i] + snow[j] });
	
	// 2️⃣ 눈사람들 키 별로 정렬
	sort(snowman.begin(), snowman.end(), cmp);

	// 3️⃣ 정렬된 snowman 을 순회하면서 각 원소를 안나 눈사람으로 설정한 후 그 뒤에 있는 것들 중 (즉, 안나보다 키 큰 눈사람) 
	// 처음으로 서로 다른 4 개의 눈덩이를 사용한 경우가 되는 눈사람을 엘사 눈사람으로 설정한 후 키 차이를 구하고 바~~~로 빠져나오면 된다.  
	// 이러면 거의 NC2 의 시간복잡도 보장할 것이다.
	int answer = INT_MAX;
	for (int i = 0; i < snowman.size() - 1; ++i) {
		Elem anna = snowman[i];
		for (int j = i + 1; j < snowman.size(); ++j) {
			Elem elsa = snowman[j];
			if (elsa.index1 != anna.index1 && elsa.index1 != anna.index2 && elsa.index2 != anna.index1 && elsa.index2 != anna.index2) {
				answer = min(answer, elsa.sum - anna.sum);
				break;
			}
		}
	}
	cout << answer;
}

🔥 두 번째 풀이 (투포인터)

코드 출처 블로그 https://velog.io/@pss407/%EB%B0%B1%EC%A4%8020366-%EA%B0%99%EC%9D%B4-%EB%88%88%EC%82%AC%EB%9E%8C-%EB%A7%8C%EB%93%A4%EB%9E%98

안나의 눈사람에 사용될 두 눈덩이를 먼저 고정시켜 놓은 후 (i와 j를 사용) 이 안나의 눈사람을 기준으로 하여, 안나의 두 눈덩이 사이 내에서 엘사 두 눈덩이를 투포인터 방식으로 결정해나간다. ((left, right를 사용) 그렇기 때문에 안나의 눈덩이는 최소 3 칸 이상 차이가 나야한다. 안나의 두 눈덩이를 고정시키는데 대략 N^2 만큼의 시간 복잡도 안에서 엘사의 두 눈덩이를 투포인터로 결정해나가기 때문에 첫번째 풀이보다는 실행 시간이 좀 더 걸릴 것이다. (엘사 안나 둘 중 누구를 투포인터를 적용할지는 중요하지 않다.)

조합을 구하듯 이중 반복문을 돌려 i 와 j를 고정하여 안나 눈사람을 정한다.(이 둘은 최소 3 이상 차이가 나야 한다.) 이 i와 j 사이의 범위에서 left, right 투포인터 알고리즘을 적용하여 엘사 눈사람을 정한다. i, j, left, right 모두 눈덩이를 가리키는 포인터가 된다.(인덱스)

✨ 투포인터 left, right 는 각각 양 끝에서 시작한다. 또한 눈덩이 배열을 오름차순 정렬을 미리 해놓는다.

• 투포인터 이동 기준 (즉, 고정된 안나의 두 눈덩이를 기준으로 엘사의 눈덩이를 어떻게 변경시켜나갈 것인가)
  • 현재의 i, j, left, right 로 두 눈사람이 모두 결정되었다면 키 차이를 구한다.
    • (snow[left] + snow[right]) - (snow[i] + snow[j])
  • 엘사 눈사람이 안나 눈사람보다 키가 크다면 (즉, 위 식의 결과가 양수)
    • 최소 차이에 도달하기 위해선 앞으로 엘사의 키가 더 작아져야 한다. 따라서 right 왼쪽으로 한칸 이동! (정렬 되어있으니 가능)
  • 엘사 눈사람이 안나 눈사람보다 키가 작다면 (즉, 위 식의 결과가 음수)
    • 최소 차이에 도달하기 위해선 앞으로 엘사의 키가 더 커져야 한다. 따라서 left 오른쪽으로 한칸 이동! (정렬 되어있으니 가능)
  • “차이” 는 절대값이어야 하는 개념이기 때문.

무작정 4 개의 눈덩이를 뽑아보는게 아닌, 안나의 두 눈덩이만 뽑아둔 후 그 기준으로 엘사의 눈덩이는 투포인터로 O(N) 으로 결정하는 방식 ! 엘사의 모든 눈덩이 경우의 수를 다 구하지 않는다. 전체적으론 대략 N^3 의 시간 복잡도가 소요될 듯 하다.

#include <bits/stdc++.h>

using namespace std;

struct Elem { int index1, index2, sum; };
bool cmp(const Elem& a, const Elem& b) {
	return a.sum < b.sum;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

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

	sort(snow.begin(), snow.end()); // 눈덩이 크기 순으로 정렬 

	int answer = INT_MAX;
	for (int i = 0; i < N - 3; ++i) {
		for (int j = i + 3; j < N; ++j) {
			// i ~ j 범위의 양끝에서 시작
			// left 와 right 는 엘사의 눈덩이
			int left = i + 1;
			int right = j - 1;

			while (left < right) {
                int anna = snow[i] + snow[j]; // 안나 눈사람
                int elsa = snow[left] + snow[right]; // 엘사 눈사람
				int result = elsa - anna;
				
				answer = min(answer, abs(result)); 
				
				if (result > 0)  // 현재 엘사가 더 크다면 최소 키 차이를 구하기 위해선 앞으로 엘사가 더 작아져야 한다.
					right = right - 1;
				else  // 현재 엘사가 더 작다면 최소 키 차이를 구하기 위해선 앞으로 엘사가 더 커져야 한다.
					left = left + 1;
			}
		}
	}
	cout << answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기