취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2980번 문제인 도로와 신호등이다.
문제는 아래 링크를 확인하자.

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

도로의 각 시작점으로부터 d만큼 떨어진 지점에 어떤 신호등이 있는지를 기록하자. 그리고 도로의 시작점부터 끝점까지 이동하는 시뮬레이션을 진행해 문제를 해결하자.

신호등이 없는 칸의 경우 빨간불이 0초 켜지고 초록불이 x(>0)초 켜지는 주기의 신호등이 있다고 가정해도 무방하다는 점을 이용하면 구현을 간편하게 할 수 있을 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, L;
int sgR[1000], sgG[1000];
int ans;

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

	cin >> N >> L;
	for (int i = 0; i < L; i++) sgG[i] = 1000000007;
	while (N--) {
		int D, R, G; cin >> D >> R >> G;
		sgR[D] = R, sgG[D] = G;
	}

	for (int i = 0; i < L; i++) {
		int tmp = ans % (sgR[i] + sgG[i]);
		if (tmp < sgR[i]) ans += sgR[i] - tmp;

		ans++;
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4657번 문제인 Image Perimeters이다.
문제는 아래 링크를 확인하자.

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

클릭으로 표시된 8방향 기준 connected component의 둘레의 길이를 구하는 문제이다.

8방향 기준 connected component는 bfs등의 그래프 탐색을 통해, 그 둘레의 길이는 connected component를 구성하는 각 칸의 주변 'X'가 아닌 칸 수를 세어 합하는 것으로 구할 수 있다

아래는 제출한 소스코드이다.

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

int R, C, sR, sC;
string board[20];
int visited[20][20];

int dr[8] = { 1,-1,0,0,1,-1,-1,1 };
int dc[8] = { 0,0,1,-1,1,1,-1,-1 };

queue<pair<int, int>> que;

void solve() {
	int ans = 0;
	memset(visited, 0, sizeof(visited));
	for (int r = 0; r < R; r++) cin >> board[r];
	
	if (board[sR][sC] == 'X') {
		visited[sR][sC] = 1;
		que.push(make_pair(sR, sC));
	}

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || visited[rr][cc] || board[rr][cc] == '.') continue;
			visited[rr][cc] = 1;
			que.push(make_pair(rr, cc));
		}
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) ans++;
			else if (board[rr][cc] == '.') ans++;
		}
	}

	cout << ans << '\n';
}

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

	cin >> R >> C >> sR >> sC;
	while (R) {
		sR--, sC--;
		solve();
		cin >> R >> C >> sR >> sC;
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8291번 문제인 Coprime Numbers이다.
문제는 아래 링크를 확인하자.

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

1의 배수의 쌍의 개수, 2의 배수의 쌍의 개수, ..., 300만의 배수의 쌍의 개수는 각각의 \(k\)에 대하여 주어진 수열의 \(k\)의 배수의 개수를 안다면 구해낼 수 있다. 모든 \(N\) 이하의 \(k\)에 대하여 주어진 수열의 \(k\)의 배수의 개수를 구하는 것은 주어질 수 있는 수의 최댓값을 \(M\)이라 할 때 에라토스테네스의 체와 같은 원리로 \(O(MlgM)\)에 해낼 수 있다.

문제의 답은 포제원리(inclusion and exclusion)에 의해 1의 배수의 쌍의 개수 - (서로 다른 소수 1개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) + (서로 다른 소수 2개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) - (서로 다른 소수 3개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) +... 와 같이 구할 수 있음을 관찰하자. 각 수에 대하여 위의 부호를 결정짓는 데 사용할 뫼비우스 함수의 값들을 먼저 구한 다음 위의 식을 계산하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
int arrcnt[3000001];
int cnt[3000001];
char mobius[3000001];
bool sieve[3000001];

ll ans;

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

	cin >> N;
	cnt[1] = N;
	while (N--) {
		int x; cin >> x;
		arrcnt[x]++;
	}
	
	for (int i = 1; i < 3000001; i++) mobius[i] = 1;
	for (int i = 2; i < 3000001; i++) {
		if (sieve[i]) {
			for (int j = i; j < 3000001; j += i) cnt[i] += arrcnt[j];
		}
		else {
			for (int j = i; j < 3000001; j += i) mobius[j] *= -1, cnt[i] += arrcnt[j], sieve[j] = 1;
			ll sq = (ll)i * i;
			for (ll j = sq; j < 3000001; j += sq) mobius[j] = 0;
		}
	}

	for (int i = 1; i < 3000001; i++) {
		ans += (ll)mobius[i] * cnt[i] * (cnt[i] - 1) / 2;
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2428번 문제인 표절이다.
문제는 아래 링크를 확인하자.

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

먼저 주어지는 파일의 크기를 오름차순으로 정렬하자. 그리고 그 순서대로 파일의 번호를 0부터 N-1까지 새로 붙이자.

이 때 i번 파일과 함께 검사해야하는 보다 용량이 작은 파일은 하나의 연속한 구간에 모여있음을 알 수 있다. 또한 그 구간의 왼쪽 끝은 i가 증가함에 따라 같이 증가함을 관찰할 수 있다.

위 관찰을 이용해 투포인터로 각 구간의 크기를 구해 문제의 답을 구하자.

용량의 90%와의 대소를 판정할 때 부동소수점 오차가 걱정된다면 0.9를 곱하는 대신 부등식의 양쪽에 9와 10을 적절히 곱해 실수연산을 피해주자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
int arr[100000];
ll ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	int L = 0;
	for (int R = 1; R < N; R++) {
		while (arr[L] * 10 < arr[R] * 9) L++;
		ans += R - L;
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2036번 문제인 수열의 점수이다.
문제는 아래 링크를 확인하자.

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

1보다 큰 양수는 큰 수부터 두 개씩 차례로 곱해 더하고 음수는 작은 수부터 두 개씩 차례로 곱해 더하는 그리디한 전략으로 문제를 해결할 수 있다.

1의 경우 다른 수와 곱해 더하는 것보다 따로 더할 때 전체 합이 1 더 커진다는 점을 놓치지 말자.

또한 문제의 답이 32비트 정수 자료형의 범위를 넘어설 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

int N;
int cnt[2];
priority_queue<int, vector<int>, greater<>> negque;
priority_queue<int> posque;

ll ans;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x > 1) posque.push(x);
		else if (x < 0) negque.push(x);
		else cnt[x]++;
	}

	while (negque.size() > 1) {
		ll val1 = negque.top(); negque.pop();
		ll val2 = negque.top(); negque.pop();
		ans += val1 * val2;
	}
	while (posque.size() > 1) {
		ll val1 = posque.top(); posque.pop();
		ll val2 = posque.top(); posque.pop();
		ans += val1 * val2;
	}

	if (posque.size()) ans += posque.top();
	if (negque.size() && !cnt[0]) ans += negque.top();
	ans += cnt[1];

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2910번 문제인 빈도 정렬이다.
문제는 아래 링크를 확인하자.

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

주어지는 각 수를 중복없이 다음과 같은 우선순위로 정렬하자.

1) 등장횟수 내림차순

2) 등장순서 오름차순

그 다음 수들을 위의 차례대로 등장횟수만큼씩 출력해 문제를 해결하자.

map, sort 등을 이용하면 구현을 편리하게 할 수 있을 것이다.

아래는 제출한 소스코드이다.

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

int N, C;
map<int, pair<int, int>> mp; // {개수,최초등장인덱스}
vector<pair<pair<int, int>, int>> vec;

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

	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (mp.count(x)) mp[x].first--;
		else mp.insert(make_pair(x, make_pair(-1, i)));
	}

	for (auto& p : mp) {
		pair<pair<int, int>, int> pp = make_pair(p.second, p.first);
		vec.emplace_back(pp);
	}

	sort(vec.begin(), vec.end());

	for (auto& p : vec) {
		while (p.first.first++) cout << p.second << ' ';
	}
}