기록을

조합과 관련된 문제라고 기억한다. 조합과 백트레킹을 매끄럽게 다룰 수 있었다면 조금 더 빠르게 풀고 넘어갈 수 있었던 문제였다. 역량테스트 A형스러운 문제였던 기억이 난다.

가장 기본적으로 소수를 판별할 수 있어야 한다.

다음으로 정수의 자리수를 없애는 방식으로 수의 변화가 일어난다. 따라서 문자열 처리를 해주면 되겠다.

정수의 자리수에서 하나의 숫자를 지우는 것을 조합의 개념으로 이해하고, 문제를 풀이했다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;
	return true;
}
int Max = -1;
int func(int n, int res) {
	
	string str = to_string(n);
	
	if (str.length() == 1) {
		if (isPrime(n)) {
			res++;
			if (Max < res) Max = res;
			//printf("\n %d 일 때 res는 %d\n", n, res);
			return res;
		}
		else {
			if (Max < res) Max = res;
			return res;
		}
	}
	
	if (isPrime(n)) {
		res++;
		if (Max < res) Max = res;
		//printf("\n %d 일 때 res는 %d\n", n, res);
	}
	else {
		//cout << n << "은 소수가 아님\n";
		if (Max < res) Max = res;
		return res;
	}
	
	//vector<int> a; //몇개의 수에서
	int a[6];
	
	for (int i = 0; i < str.length(); i++) {
		a[i] = stoi(str.substr(i, 1));
	}
	
	int select[7] = { 0,1,1,1,1,1,1 };
	
	do {
		string temp;
		for (int i = 0; i < str.length(); i++) {
		
			if (select[i])
				temp = temp + to_string(a[i]);
		}
		//cout << temp << ' ' << res << '\n';
		func(stoi(temp.substr(0,temp.length())),res);
	}while (next_permutation(select, select + str.length()));

}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	for (int T = 1; T <= tc; T++) {
		cout << "Case #" << T << '\n';
		Max = -1;
		int a, b;
		cin >> a >> b;
		func(a, 0);
		int MaxA = Max;
		Max = -1;
		func(b, 0);
		int MaxB = Max;

		//printf("Amax = %d Bmax = %d\n", MaxA, MaxB);
		if (MaxA > MaxB)
			cout << 1 << '\n';
		else if (MaxA < MaxB)
			cout << 2 << '\n';
		else
			cout << 3 << '\n';
	}
	return 0;
}

dp문제였다. 자세한 복기는 문제가 업로드된 이후에 해보겠다.

#include <iostream>

using namespace std;
int d[1000001];
int Answer;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//setbuf(stdout, NULL); //주석풀고제출

	int T, test_case;
	
	d[2] = 1;

	int i = 4;
	while (i <= 1000000) {
		if (i % 2 == 0) {
			d[i] = d[i / 2] + 1;
			i--;
			continue;
		}
		else {
			d[i] = d[i + 1] + 1;
			i += 3;
			continue;
		}
	}

	cin >> T;
	
	for (test_case = 0; test_case < T; test_case++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		Answer = 0;
		
		for (int i = n1; i <= n2; i++) {
			Answer = Answer + d[i];
		}
		
		cout << "Case #" << test_case + 1 << '\n';
		cout << Answer << '\n';
	}

	return 0;
}

직사각형이 장애물로 존재하는 곳을 굴러가는 원의 자취에 관한 문제였던 것으로 기억한다.

자세한 복기는 문제가 공식적으로 업로드된 이후에 하도록 하겠다.

#define _USE_MATH_DEFINES
#include <iostream>
#include<math.h>
#include<iomanip>
using namespace std;

double dis;

int main(int argc, char** argv)
{
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	//setbuf(stdout, NULL); //주석풀고제출

	int T, test_case;

	cout << fixed;
	cout.precision(12);


	cin >> T;
	
	for (test_case = 0; test_case < T; test_case++)
	{
		double r, st, en;
		cin >> r >> st >> en;
		double blk;
		cin >> blk;

		dis = 0;

		while (blk--) {
			double lef, rig, h;
			cin >> lef >> rig >> h;
			
			if (h >= r) {
				
				dis = dis + ((lef - r) - st); // 시작점에서 왼쪽가로
				dis = dis + (h - r) * 2;
				dis = dis + (r * M_PI);
				dis = dis + rig - lef;
				st = rig + r; //시작점 이동
			}
			else {
				double temp = sqrt(pow(r, 2) - pow(r - h, 2));
				dis = dis + (lef - temp - st);
				dis = dis + rig - lef;
				double angle = atan2(temp, r - h);
				dis = dis + angle * r * 2 ;
				st = rig + temp;
			}
			
		}
		dis = dis + en - st;

		cout << "Case #" << test_case + 1 << '\n';
		cout << dis << '\n';
	}

	return 0;
}

(문제 설명)

1001과 같은 수처럼 앞에서 읽은 것이 뒤에서 읽은 것과 같은 수를 회문인 수라고 한다.

1 <= n <= 10,000 인 정수 n이 주어질 때, 세 개 이하의 회문인 수의 합으로 n이 표현될 수 있는지 여부를 판단하는 문제이다.

예시로 그 수들을 쭉 구해보면 알 수 있는데, 몇개 되지 않는다.

따라서 초기에 모두 구해두고 O(n^3)으로 해결했다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
vector<int> v; //회문수 벡터
int res[3];
int fir(int n) {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == n) {
			cout << 1 << ' ' << v[i] << '\n';
			return 1;
		}
	}
	return 0;
}
int sec(int n) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			if (v[i] + v[j] == n) {
				cout << 2 << ' ' << v[j] << ' ' << v[i] << '\n';
				return 1;
			}
		}
	}
	return 0;
}
int thi(int n) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			for (int k = 0; k < v.size(); k++) {
				if (v[i] + v[j] + v[k] == n) {
					cout << 3 << ' ' << v[k] << ' ' << v[j] << ' ' << v[i] << '\n';
					return 1;
				}
			}
		}
	}
	return 0;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		int n;
		cin >> n;
		//모든 회문수 구하기
		
		for (int i = 1; i <= 10000; i++) {
			string str = to_string(i);
			int len = str.length();
			bool isCir = true;
			for (int j = 0; j < len/2; j++) {
				if (str[j] != str[len - 1 - j]) {
					isCir = false;
					break;
				}
			}
			if (isCir)
				v.push_back(i);
		}
		
		cout << "Case #" << t << '\n';
		if (fir(n) == 1)
			continue;
		else if (sec(n) == 1)
			continue;
		else if (thi(n) == 1)
			continue;
		else
            cout << 0 << '\n';
	}
	return 0;
}

문제 설명

-n명의 선수들의 실력이 입력으로 주어진다.

-실력차이가 k이하인 선수들은 같은 버스에 타고 있을 수 없다.

-이 때 필요한 버스의 수는?

풀이

처음에는 벡터에 pair을 담는 형태로 선수 정보와 버스 정보를 담으려고 했다.

이 방식으로 하면 새로운 선수에 대한 처리를 할 때마다, 이전의 선수들에 대한 정보를 모두 검사해야 한다.

하지만 n < 200,000이기 때문에 O(N) 못해도 O(nlogn)에는 해결하겠다는 생각으로 접근해야 할 것이다.

기본 아이디어는 선수들의 실력을 오름차순으로 정렬하는 것이다.

정렬된 배열 1 3 4 5 7 9 를 선수 정보라고 치고, k = 3이라고 한다면

3은 1과 같은 버스에 탈 수 없다. (3 - 1 < k ) 3까지 확인한 결과로 버스는 두대가 필요하다.

4를 확인할 때, 이미 두대가 필요한 것을 알고 있으므로 두칸 앞으로가서 1부터 비교한다. 1과도 같은 버스에 탈 수 없기 때문에 버스는 한대가 더 추가된다. 1과도 같이 탈 수 없으면, 정렬된 상태이기 때문에 1보다 더 큰 실력을 가진 사람과는 비교할 필요도 없는 것이다.

5를 확인할 때 이미 세대가 필요하다는 것을 알고있으므로 세칸 앞으로 가서 1부터 확인한다. 1과 5는 같은 버스에 탈 수 있다.

이런식으로 진행해주면 된다.

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

int arr[200001];
int main(void) {

	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {

		int n, k;
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		sort(arr, arr + n); //오름차순 정렬
		
		int bus = 1;

		for (int i = 1; i < n; i++) {
			if (arr[i] - arr[i - bus] <= k)
				bus++;
		}
		cout << "Case #" << t << '\n' << bus << '\n';
	}
	return 0;
}