2018 삼성 SCPC 1차 문제풀이

2018 SCPC

총 5문제고 예선문제라서 그리 어렵지는 않도록 했나보다. 나는 나동빈님의 유투브 강의를 보면서 진행했는데 기존에 쓰던 python언어를 쓸수없고 c++을 써야되어서 조금 부담이 되긴했다. 그치만 도전하는건 멈추고 싶지않아서 어찌됐건 보려고 한다. 갈리면서 성장한다고 믿기에! 내일 2021 SCPC가 있기에 그것을 대비하고자 준비를 하는것이다. 이제 문제풀이를 본격 해보겠다.

문제 1.버스 타기(greedy)

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

int main() {
	int T, testCase;
	cin >> T;

	for (testCase = 1; testCase <= T; testCase++) {
		int n, k;
		cin >> n >> k;
		vector<int>a;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			a.push_back(x);
		}
		sort(a.begin(), a.end());
		int result = 1;
		for (int i = 1; i < n; i++) {
			if (a[i] - a[i - result] <= k)result++;
		}
		cout << "CASE #" << testCase << "\n";
		cout << result << "\n";

	}
	return 0;
}

문제 2.회문인 수의 합(brute force)

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

int circular[10001];
int cnt;

bool isPalindrome(int x) {
	stringstream ss;
	ss << x;
	string str = ss.str();
	int len = str.length();
	for (int i = 0; i < len; i++) {
		if (str[i] != str[len - 1 - i])
			return false;
		return true;
	}
}

bool one(int x) {
	for (int i = 0; i < cnt; i++) {
		if (circular[i] == x) {
			cout << 1 << " " << circular[i] << "\n";
			return true;
		}
	}
	return false;
}

bool two(int x) {
	for (int i = 0; i < cnt; i++) {
		for (int j = 0; j < cnt; j++) {
			if (circular[i] + circular[j] == x) {
				cout << 2 << " " << circular[j] <<" "<< circular[i] << "\n";
				return true;
			}
		}
	}
	return false;
}

bool three(int x) {
	for (int i = 0; i < cnt; i++) {
		for (int j = 0; j < cnt; j++) {
			for (int k = 0; k < cnt; k++) {
				if (circular[i] + circular[j]+circular[k] == x) {
					cout << 2 << " " <<circular[k]<<" "<< circular[j] << " " << circular[i] << "\n";
					return true;
				}
			}
		}
	}
	return false;
}

int main(void) {
	int T, testCase;
	for (int i = 0; i <= 10000; i++) {
		if (isPalindrome(i)) {
			circular[cnt] = i;
			cnt++;
		}
	}
	cin >> T;
	for (testCase = 1; testCase <= T; testCase++) {
		int n;
		cin >> n;
		cout << "Case #" << testCase << "\n";
		if (!one(n) && !two(n) && !three(n)) {
			cout << "0" << "\n";
		}
	}
}

문제 3.우주정거장(dfs)

#include<iostream>
#include<vector>
#include<queue>
#define MAX 200001
using namespace std;

vector<int> a[MAX];
queue<int> q;
int result;

//idea=>연결된 간선이 2개인 모든 노드 중에서 삼각형 사이클을 형성하는 노드를 큐에 담아서 계속해서 지워나가면 해결 가능!
//결국 cycle찾는 과정이 vectorDrop,process,find에 나와있는 것이다.

//벡터에서 특정한 원소를 찾아 제거한다.
void vectorDrop(int now, int target) {
	for (int i = 0; i < a[now].size(); i++) {
		if (a[now][i] == target) {
			a[now].erase(a[now].begin() + i);
		}
	}
}

//삼각형 사이클을 발견했을때 처리하는 함수다.
void process(int target) {
	vectorDrop(a[target][0], target);
	vectorDrop(a[target][1], target);
	if (a[a[target][0]].size() == 2) {
		q.push(a[target][0]);
	}
	if (a[a[target][1]].size() == 2) {
		q.push(a[target][1]);
	}
}

//dfs를 이용해 삼각형 사이클을 찾는다.
void find(int target, int now, int cnt) {
	if (cnt == 3) {
		for (int i = 0; i < a[now].size(); i++) {
			//삼각형 사이클이 형성되는 경우
			if (a[now][i] == target) {
				result++;
				process(target);
				return;
			}
		}
		return;
	}
	//연결된 노드를 dfs 탐색한다.
	for (int i = 0; i < a[now].size(); i++) {
		find(target, a[now][i], cnt + 1);
	}
}

int main(void) {
	int T;
	cin >> T;
	for (int testCase = 1; testCase <= T; testCase++) {
		for (int i = 0; i < MAX; i++) {
			a[i].clear();
		}
		result = 0;
		queue<int>empty;
		swap(q, empty);
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			a[x].push_back(y);
			a[y].push_back(x);
		}

		//연결된 간선이 2개인 노드를 큐에 삽입한다.
		for (int i = 1; i <= n; i++) {
			if (a[i].size() == 2) {
				q.push(i);
			}
		}

		//큐가 비워질 때까지 사이클을 찾아 처리한다.
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			find(x, x, 1);
		}
		cout << "Case #" << testCase << "\n";
		cout << n - result << "\n";

	}
	return 0;
}

+) 4번같은 경우는 만점자가 거의 드물었고 5번은 이해를 못했다.🤣 이해하고나서 추가해보도록 하자.

참고한 사이트> https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221305544177