백준 2422 [C++] - 시간초과

www.acmicpc.net/problem/2422

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

1. 풀이방법 

 

- 1~N까지의 모든 아이스크림 중 3개를 만드는 모든 조합을 골라서

 

- 이게 가능한지 (최악의 조합에 속하는 것이 없는 지) 를 확인 후 방법의 수를 증가시켜 주면되는 문제였습니다.

 

- 조합을 만드는 것은 어렵지 않았고, 처음에는 최악의 조합을 <pair<int,int>>로 만들어

 

- 반복문을 통해서 psice() 가능한 아이스크림조합인지를 확인 했었는데, 시간초과가 발생하였습니다.

 

- 반복문 탐색 중 정지 조건 break 를 걸어 주고 난 뒤 제출해도 역시 시간초과 였습니다.

 

- 그래서 이차원배열을 선언하여 두 아이스크림이 최악의 조합인지를 O(1) 시간에 확인할 수 있도록

 

- 수정하여 제출 하였더니 통과 되었습니다.

 

- 그래프 구현방법 중 인접행렬 방식( 두 노드가 인접했는지 확인하는 것이 매우 빠르다라는 장점)

 

- 으로 부터 나온 생각으로 구현하였습니다.

 

 

 

2. 주의사항

 

- 문제 자체는 쉬웠지만, 시간을 단축하는 부분에 있어 특이점이 있는 것 같아 포스팅으로 남깁니다.

 

 

 

3. 나의코드 

 

- 주석 부분은 반복문을 통한 탐색 부 입니다.

 

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

int N;
int M;
int t1, t2;
// vector<pair<int, int>> worstice;
bool wi[201][201];
vector<int> icearr;
int pscase = 0;

/*bool psice() {
	for (int i = 0; i < worstice.size(); i++) {
		int tmp = 0;
		for (int j = 0; j < icearr.size(); j++) {
			if (icearr[j] == worstice[i].first || icearr[j] == worstice[i].second) {
				tmp++;
			}
			if (tmp == 2) return false;
			if (icearr[j] > worstice[i].second) break;
		}
	}
	return true;
}*/
bool ps() {
	if (wi[icearr[0]][icearr[1]] == true || wi[icearr[0]][icearr[2]] == true
		|| wi[icearr[1]][icearr[2]] == true) return false;
	else return true;
}

void makeice(int index,int cnt) {
	if (cnt == 3) {
		if (ps()) {
			pscase++;
		}
		return;
	}
	for (int i = index; i <= N; i++) {
		icearr.push_back(i);
		makeice(i+1,cnt + 1);
		icearr.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2;
		// worstcase.push_back({t1,t2});
		wi[t1][t2] = true;
		wi[t2][t1] = true;
	}
	makeice(1,0);

	cout << pscase << "\n";

	return 0;
}