Feel Coding

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

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


int main() {
	while (true) {
		string s;
		cin >> s;
		if (s == "end") break;
		bool flag = false;
		int countVowel = 0;
		vector<bool> isVowel(s.size());
		
		if (s[0] == 'a' || s[0] == 'e' || s[0] == 'i' || s[0] == 'o' || s[0] == 'u') {
			countVowel++;
			isVowel[0] = true;
		}
		for (int i = 1; i < s.size(); i++) {
			if (s[i] != 'e' && s[i] != 'o' && s[i - 1] == s[i]) {
				flag = true;
				break;
			}
			if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
				countVowel++;
				isVowel[i] = true;
			}
		}
		if (flag || countVowel == 0) {
			cout << '<' << s << "> is not acceptable.\n";
			continue;
		}
		for (int i = 2; i < s.size(); i++) {
			if (isVowel[i - 2] == isVowel[i - 1] && isVowel[i - 1] == isVowel[i]) {
				flag = true;
				break;
			}
		}
		if(flag) cout << '<' << s << "> is not acceptable.\n";
		else cout << '<' << s << "> is acceptable.\n";
	}
	return 0;
}

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

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	for (int a = 2; a <= 100; a++) {
		for (int b = 2; b < a; b++) {
			for (int c = b; c < a; c++) {
				for (int d = c; d < a; d++) {
					if (pow(a, 3) == pow(b, 3) + pow(c, 3) + pow(d, 3)) {
						cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")\n";

					}
				}
			}
		}
	}
	return 0;
}

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

#include <iostream>
#include <tuple>
#include <vector>
#include <map>
#include <queue>
using namespace std;


int main() {
	int numOfPeople, m, l;
	cin >> numOfPeople >> m >> l;
	vector<int> count(numOfPeople);
	int currentPerson = 0;
	count[currentPerson] = 1;
	int ballTossCount = 0;
	while (true) {
		ballTossCount++;
		if (count[0] % 2 == 0) {
			currentPerson = (currentPerson - l + numOfPeople) % numOfPeople;
		}
		else {
			currentPerson = (currentPerson + l) % numOfPeople;
		}
		count[currentPerson]++;
		if (count[currentPerson] == m) break;
	}
	cout << ballTossCount;
	return 0;
}

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

#include <iostream>
using namespace std;


int main() {
	int n;
	cin >> n;
	for (int i = n; i >= 4; i--) {
		int numerator = i;
		int flag = false;
		while (numerator != 0) {
			if (numerator % 10 == 4 || numerator % 10 == 7) {
				numerator /= 10;
			}
			else {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << i;
			return 0;
		}
	}
	return 0;
}

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

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

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end(), cmp);
	int maxDay = 0;
	for (int i = 0; i < v.size(); i++) {
		v[i] = v[i] + i + 2;
		if (v[i] > maxDay) maxDay = v[i];
	}
	cout << maxDay;
	return 0;
}

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

#include <iostream>
#include <tuple>
#include <vector>
#include <map>
using namespace std;

map<char, pair<char, char>> m;

void preorder(char root) {
	cout << root;
	if (m[root].first != '.')
		preorder(m[root].first);
	if (m[root].second != '.')
		preorder(m[root].second);
}
void inorder(char root) {
	if (m[root].first != '.')
		inorder(m[root].first);
	cout << root;
	if (m[root].second != '.')
		inorder(m[root].second);
}
void postorder(char root) {
	if(m[root].first != '.')
		postorder(m[root].first);
	if(m[root].second != '.')
		postorder(m[root].second);
	cout << root;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char root, left, right;
		cin >> root >> left >> right;
		m[root] = make_pair(left, right);
	}
	preorder('A');
	cout << '\n';
	inorder('A');
	cout << '\n';
	postorder('A');
	return 0;
}

자료구조 시간에 배운 것과 이런 문제를 풀 때 사용하는 자료구조에는 조금 거리가 있는 것 같다.

트리 구조체나 클래스를 직접 만들지 않아도 이렇게 풀 수 있다.

https://breakcoding.tistory.com/205

처음에는 이진트리 클래스를 직접 만들었었는데 insert하는 과정에서 위상정렬을 해야 트리에 노드를 삽입할 수 있었다.

따라서 그냥 편리하게 map을 만들었다. 다른 사람들은 어떻게 트리를 구현했는지 찾아봐야겠다.

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

문제 자체는 어렵지 않았는데 출력 형식 조정하느라 애를 먹었다.

처음에는 for문을 0부터 9까지 돌리면서 cout << n << setprecision(10) << sum <<'\n'; 했는데 틀려서

for문을 0부터 9까지 돌리면서 cout << n << " " << fixed << setprecision(9) << sum << '\n'; 했는데 또 틀렸다.

결국은 for를 둘로 나눠서 출력했더니 맞았다.

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

int main() {
	cout << "n e" << '\n';
	cout << "- -----------" << '\n';
	for (int n = 0; n <= 2; n++) { //n
		double sum = 0;
		for (int i = 0; i <= n; i++) {
			int denominator = 1;
			for (int j = i; j > 0; j--) {
				denominator *= j;
			}
			sum += (1 / (double)denominator);
		}
		cout << n << " " << sum << '\n';
	}
	for (int n = 3; n <= 9; n++) { //n
		double sum = 0;
		for (int i = 0; i <= n; i++) {
			int denominator = 1;
			for (int j = i; j > 0; j--) {
				denominator *= j;
			}
			sum += (1 / (double)denominator);
		}
		cout << n << " " << fixed << setprecision(9) << sum << '\n';
	}
	return 0;
}

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

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


int main() {
	int fee[3];
	for (int i = 0; i < 3; i++) {
		cin >> fee[i];
	}
	int arriveTime[3];
	int leaveTime[3];
	vector<pair<int, int>> time;
	for (int i = 0; i < 3; i++) {
		cin >> arriveTime[i];
		cin >> leaveTime[i];
		time.push_back(make_pair(arriveTime[i], 1));
		time.push_back(make_pair(leaveTime[i], -1));
	}
	sort(time.begin(), time.end());
	int count = 1;
	int totalFee = 0;
	int previousTime = time[0].first;
	for (int i = 1; i < 6; i++) {
		int feePerHour = fee[count - 1];
		int now = time[i].first;
		totalFee += ((now - previousTime) * feePerHour * count);
		count += time[i].second;
		previousTime = time[i].first;
 	}
	
	cout << totalFee;
	return 0;
}

어제도 그래놓고는.. 오늘도 다짐한다. 문제를 똑바로 읽자.

트럭 1대면 A원, 2대면 B원, 3대면 C원인 줄 알았는데 한 대당 A원, B원, C원이었다.

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

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


int main() {
	int vacationDays, koreanTotal, mathTotal, koreanMaxPage, mathMaxPage;
	cin >> vacationDays >> koreanTotal >> mathTotal >> koreanMaxPage >> mathMaxPage;
	int days = 1;
	while (true) {
		koreanTotal -= koreanMaxPage;
		mathTotal -= mathMaxPage;
		if (koreanTotal <= 0 && mathTotal <= 0) break;
		days++;
	}
	cout << vacationDays - days;
	return 0;
}

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

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

int n;
bool foundAnswer = false;

void select(vector<int> result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		string s = "";
		for (int i = 0; i < n; i++) {
			s += to_string(result[i]);
		}
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (s.substr(i, j) == s.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		for (int i = 0; i < n; i++) {
			cout << result[i];
		}
		return;
	}
	for (int i = 1; i <= 3; i++) {
		result[num] = i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	vector<int> result(n);
	select(result, 0);
	return 0;
}

시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		result[num] = '1' + i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

애초에 string으로 해보았다. 이것도 시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 2; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		if (num == 0) {
			result[num] = '1' + i;
			select(result, num + 1);
		}
		else {
			if (result[num - 1] == '1' + i) continue;
			result[num] = '1' + i;
			select(result, num + 1);
		}
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

재귀호출 전에 인접한 것이 같으면 재귀호출을 안 하도록 했는데 이것도 시간초과