굳건하게

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

[알고리즘풀이]

"네 변의 길이가 같고, 대각선의 길이가 같다면 정사각형이다."

위 명제를 이용해 문제를 해결할 수 있다.

4개의 점에 대해서, 각 점들과의 거리를 모두 구하면 총 6개의 거리가 생긴다.

이때, 거리를 sort 하면 앞에 4개는 네 변의 길이가 되고, 뒤에 2개는 대각선의 길이가 된다. (대각선이 더 기므로)

따라서, 앞 4개의 길이가 같고 뒤 2개의 대각선의 길이가 같으지만 체크하면 된다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

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

	int t;
	cin >> t;
	while (t--) {
		vector<pair<int, int>> p;
		vector<int> s;
		for (int i = 0; i < 4; i++) {
			int a, b;
			cin >> a >> b;
			p.push_back(make_pair(a, b));
		}
		for (int i = 0; i < 4; i++) {
			for (int j = i + 1; j < 4; j++) {
				s.push_back((p[i].first - p[j].first) * (p[i].first - p[j].first) + (p[i].second - p[j].second) * (p[i].second - p[j].second));
			}
		}
		sort(s.begin(), s.end());
		if (s[0] == s[1] && s[1] == s[2] && s[2] == s[3] && s[4] == s[5])
			cout << "1\n";
		else
			cout << "0\n";
	}
}

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

[알고리즘풀이]

DP 문제로 다음과 같이 배열을 정의하면 된다.

Dp[i][j] : i번 째 수까지 이용해서 j 를 만들 수 있는 경우의 수.

그럼, 다음과 같은 점화식이 성립합니다.

Dp[i][j] = Dp[i - 1][j + N[i]] + Dp[i - 1][j - N[i]]

i번 째 수까지 이용해서 j를 만드는 경우의 수는

(i - 1)번 째 수까지 이용해서 (j + N[i])를 만든 경우의 수에 N[i] 를 빼는 경우와

(j - N[i])를 만든 경우의 수에 N[i]를 더하는 경우로 나눠서 생각할 수 있다.

#include<iostream>

using namespace std;

long long dp[100][21];

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

	long long n, N[100];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> N[i];
	
	dp[0][N[0]] = 1;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 0; j <= 20; j++) {
			if (0 <= j + N[i] && j + N[i] <= 20)
				dp[i][j] += dp[i - 1][j + N[i]];
			if (0 <= j - N[i] && j - N[i] <= 20) 
				dp[i][j] += dp[i - 1][j - N[i]];
		}
	}
	cout << dp[n - 2][N[n - 1]];
}

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

[알고리즘풀이]

L 부터 R 까지의 수 중에서 8이 제일 적은 수를 찾는 문제다.

먼저, L 과 R의 자릿수가 다르다면 무조건 8을 하나도 안쓰는 수를 만들 수 있다.

ex) L은 3자리, R은 4자리 숫자이면 사이에는 1000이 무조건 존재한다.

L 과 R의 자릿수가 같다면, 자릿수가 큰 쪽부터 순회를 해주며 check를 해야 된다.

i번 째 자릿수인 L[i] 와 R[i] 가 모두 8이라면 i번 째 자릿수는 8이 와야 된다.

하지만, 그전에 L[j] 와 R[j] (j < i) 에서 숫자가 다른 적이 있다면 i번 째 값은 항상 8이 아닌 사이에 있는 수를 집어넣을 수 있다.

ex)

78 88 에서 첫 번째 자릿수가 7과 8로 다르므로, 그 뒤에 자릿수는 8이 아닌 다른 사이에 있는 수를 무조건 넣을 수 있다.

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string L, R;
	cin >> L >> R;

	int ans = 0;
	if(L.length() == R.length()){
		bool flag = false;
		for (int i = 0; i < L.length(); i++) {
			if (L[i] != R[i])
				flag = true;
			if (flag)
				continue;
			if (L[i] == R[i] && L[i] == '8')
				ans++;
		}
	}
	cout << ans;
}

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

[알고리즘풀이]

먼저, 문제를 푸는데 필요한 아이디어를 정리하겠습니다.

1. 시계를 앞으로 돌린다는 뜻은 시간을 더해주는 것이고 시계를 뒤로 돌린다는 뜻은 시간을 빼준다는 뜻입니다.
2. 모든 시간은 초 단위로 표현할 수 있다.
3. 하루는 86400초이고, 우리는 24시간 단위로 답을 표현해야하므로, 하루가 넘어가는 시간에 대해서는 신경쓸 필요가 없다. 즉 현재 시간(초)= 현재시간(초) % 86400이 성립한다.

위의 3가지 사실을 이용해서, 현재 시간 h(시간) m(분) s(초)를 입력받으면 초 단위로 변환해 cur에 저장합니다.

그리고 3가지 쿼리에 대해 다음과 같이 수행합니다.

1) 시계를 앞으로 c초 만큼 돌린다.

c를 입력받고, 현재 시간(초) 에 더하고 % 86400을 취하면 현재 시간이 됩니다.

2) 시계를 뒤로 c로 만큼 돌린다.

c를 입력받고, 현재 시간(초) 에 뺍니다. 이때, 현재 시간이 음수가 된다면 86400을 계속 더해 양수로 바꿔줍니다.

3) 현재 시간을 출력하시오.

h = cur / 3600

m = (cur / 60) % 60

s = cur % 60 이 성립합니다.

이 문제는 시간을 초 단위로 다루면 간단하게 풀 수 있습니다.

#include<iostream>

#define day 86400

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, m, s, cur, tc, x, y;
	cin >> h >> m >> s >> tc;
	cur = 3600 * h + 60 * m + s;
	for (int i = 0; i < tc; i++) {
		cin >> x;
		if (x == 3)
			cout << cur / 3600 << ' ' << (cur / 60) % 60 << ' ' << cur % 60 << '\n';
		else if (x == 1) {
			cin >> y;
			cur = (cur + y) % day;
		}
		else {
			cin >> y;
			cur = (cur - y) % day;
			while (cur < 0) {
				cur += day;
			}
		}
	}
}