굳건하게

문제 : https://www.acmicpc.net/problem/1212

[알고리즘풀이]

8진수 1칸은 2진수 3칸으로 바꿀 수 있다.

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string input;
	cin >> input;
	for (int i = 0; i < input.length(); i++) {
		int t = input[i] - '0', tl[3];
		for (int j = 0; j < 3; j++) {
			tl[j] = t % 2;
			t /= 2;
		}
		if (i == 0) {
			if (tl[2] == 0 && tl[1] == 0)
				cout << tl[0];
			else if (tl[2] == 0)
				cout << tl[1] << tl[0];
			else
				cout << tl[2] << tl[1] << tl[0];
		}
		else {
			for (int j = 2; j >= 0; j--)
				cout << tl[j];
		}
	}
}

문제 : https://www.acmicpc.net/problem/8912

[알고리즘풀이]

Input 크기가 작아서 단순 구현하면 되는 문제다.

#include<iostream>

using namespace std;
int list[1000];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	int test_case;
    cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		int ninput;
        cin >> ninput;
		int total = 0;
		for (int j = 0; j < ninput; j++){
            cin >> list[j];
			for (int k = 0; k < j; k++) {
				if (list[k] <= list[j])
					total++;
			}
		}
        cout << total << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/9093

[알고리즘풀이]

getline 함수를 이용해 띄어쓰기까지 포함해서 입력을 받고, buffer flush를 이용해 buffer를 비워준다.

#include<iostream>
#include<string>
#include<vector>

using namespace std;

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

	int t;
	cin >> t;
	string bufferflush;
	getline(cin, bufferflush);
	while (t--) {
		string input, temp;
		vector<string> s;
		getline(cin, input);
		for (int i = 0; i < input.length(); i++) {
			int start = i;
			while (i < input.length() && input[i] != ' ') {
				i++;
			}
			for (int j = i - 1; j >= start; j--) {
				cout << input[j];
			}
			if (i != input.length())
				cout << ' ';
			else
				cout << '\n';
		}
	}
}

문제 : https://www.acmicpc.net/problem/4355

[알고리즘풀이]

정수론 시간에 배운 Euler Phi Function(오일러 파이 함수)를 이용해서 답을 도출할 수 있었습니다.

오늘은 간략하게 설명하고, 다음에 오일러 파이 함수는 따로 포스팅을 해보도록 하겠습니다.

양의 정수 N이 다음과 같이 소인수분해가 된다고 한다면, 

N과 서로소인 수의 갯수 = Euler_Phi(N) 은 다음과 같습니다.

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

bool era[100001];

long long euler_phi(int n) {
	// 먼저 n을 소인수분해해야된다.
	vector<int> v, c;
	long long answer = 1;
	for (int i = 2; i <= 100000; i++) {
		if (era[i] == false && n % i == 0) {
			v.push_back(i);
			int count = 0;
			while (n % i == 0) {
				n /= i;
				count++;
			}
			c.push_back(count);
		}
	}
	
	for (int i = 0; i < v.size(); i++) {
		answer *= ((int)(pow(v[i], c[i])) - (int)(pow(v[i], c[i] - 1)));
	}
	if (n == 1)
		return answer;
	else
		return answer * (n - 1);
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 2; i <= 100000; i++) {
		if (era[i] == false) {
			for (int j = 2 * i; j <= 100000; j += i)
				era[j] = true;
		}
	}

	while (1) {
		int n;
		cin >> n;
		if (n == 0)
			return 0;
		cout << euler_phi(n) << '\n';
	}
}