기록을

가령 상황을 하나 혹은 두 개의 배열로 나타낼 수 있다고 하자.

배열이 하나라면, index 0부터 최댓값을 담는 배열을 만들고,

가장 끝 index부터 최댓값을 담는 배열을 만들고, 상황에 맞게 사용하는 것이다.

꼭 최댓값이 아니더라도, 한쪽에서는 최대, 다른 한쪽에서는 최소를 잡을 수도 있겠다.

이런 유사한 방식을 세번 이상 사용한 것 같다. 아마 다른 사람이 보면 이게 무슨 말인가 싶겠지만,

일단 내가 기억하고자 하는 목적으로 정리를 해두겠다.

#define ll long long
#include<iostream>
#include<vector>
using namespace std;

ll lmax[300001], rmin[300001];
int solution(vector<int> &T) {
	ll Max = T[0];
	for (int i = 0; i < T.size(); i++) {
		if (T[i] > Max)
			Max = T[i];
		lmax[i] = Max;
	}

	ll Min = T.at(T.size() - 1);
	for (int i = T.size() - 1; i >= 0; i--) {
		if (T[i] < Min)
			Min = T[i];
		rmin[i] = Min;
	}

	for (int i = 0; i < T.size() - 1; i++) {
		if (lmax[i] < rmin[i + 1]) {
			//len = i + 1;
			return i + 1;
		}
	}
}
int main(void) {
	vector<int> vec{ -5, -5, -5, -42, 6, 12 };
	solution(vec);
	return 0;
}

주어진 배열에서, 조건에 따라 부분 배열을 찾는 문제이다. vec 벡터를 두 개의 벡터로 나눌 것인데, 하나의 벡터의 모든 성분이 또 다른 벡터의 어떤 성분보다도 작도록 벡터를 양분하려고 할 때, 위와 같은 방법을 사용할 수 있다.

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;
}

https://www.welcomekakao.com/learn/courses/30/lessons/42748

벡터에 담긴 수를 잘라서 정렬 이후에, 주어진 index의 데이터를 벡터에 담아서 반환하면 되는 문제이다.

문제에서는 index의 시작을 1로 보고 있다는 것만 주의하면 되는 문제이다.

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;

	for (int i = 0; i < commands.size(); i++) {
		vector<int> temp;
		for (int j = commands[i][0]-1; j <= commands[i][1]-1; j++) {
			temp.push_back(array[j]);
		}
		sort(temp.begin(), temp.end());
		answer.push_back(temp[commands[i][2] - 1]);
		temp.clear();
	}
	return answer;
}

(문제 설명)

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;
}