취미로 코딩하기

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

이번에 볼 문제는 백준 2567번 문제인 색종이 - 2이다.
문제는 아래 링크를 확인하자.

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

도화지를 크기 100x100의 배열로 나타내자. 그리고 붙인 색종이로 덮인 영역을 1, 그렇지 않은 영역을 0으로 배열에 표현하자.

위와 같이 도화지를 나타내면 색종이가 붙은 영역의 둘레는 배열의 1이 있는 칸의 주변(상하좌우) 0의 개수들을 구하는 문제로 바꿔 생각할 수 있다.

입력의 크기가 충분히 작으므로 모든 색종이에 대하여 각각이 도화지에서 차지하는 칸을 1로 직접 표현하는 구현을 하여도 문제를 충분히 해결할 수 있다. 각 칸에 색종이가 덮고 있다고 표현하는 횟수는 많아야 1만번임을 확인하자.

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

#include <iostream>
using namespace std;

int N;
int board[102][102];
int ans;

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

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		x++, y++;
		for (int r = 0; r < 10; r++) {
			for (int c = 0; c < 10; c++) {
				board[x + r][y + c] = 1;
			}
		}
	}

	for (int r = 1; r < 101; r++) {
		for (int c = 1; c < 101; c++) {
			if (board[r][c]) {
				ans += 4 - (board[r - 1][c] + board[r][c + 1] + board[r + 1][c] + board[r][c - 1]);
			}
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 2578번 문제인 빙고이다.
문제는 아래 링크를 확인하자.

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

새로운 수를 사회자가 부를 때마다 (1) 빙고판에서 해당 수를 지우고 (2) 현재 지워진 수로 3개의 줄이 만들어졌는지를 체크하는 것을 시뮬레이션해 문제를 해결하자.

이 문제의 경우 칸의 수가 충분히 적으므로 비효율적이더라도 단순하고 확실한 구현을 사용해 문제를 편하게 해결해도 좋다.

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

#include <iostream>
using namespace std;

int board[5][5];
int ans;

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

	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 5; c++) cin >> board[r][c];
	}

	while (1) {
		ans++;
		int x; cin >> x;
		for (int r = 0; r < 5; r++) {
			for (int c = 0; c < 5; c++) {
				if (board[r][c] == x) board[r][c] = 0;
			}
		}

		int cnt = 0;
		for (int r = 0; r < 5; r++) {
			bool chk = 1;
			for (int c = 0; c < 5; c++) {
				if (board[r][c]) chk = 0;
			}
			if (chk) cnt++;
		}
		for (int c = 0; c < 5; c++) {
			bool chk = 1;
			for (int r = 0; r < 5; r++) {
				if (board[r][c]) chk = 0;
			}
			if (chk) cnt++;
		}
		
		bool chk = 1;
		for (int r = 0; r < 5; r++) {
			if (board[r][r]) chk = 0;
		}
		if (chk) cnt++;

		chk = 1;
		for (int r = 0; r < 5; r++) {
			if (board[r][4 - r]) chk = 0;
		}
		if (chk) cnt++;

		if (cnt > 2) {
			cout << ans << '\n';
			break;
		}
	}
}

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

이번에 볼 문제는 백준 29131번 문제인 Хобби이다.
문제는 아래 링크를 확인하자.

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

어떤 가상의 직선이 평면을 쓸고 가는 경우를 상상해보자. 단, 이 직선은 같은 점을 두 번 이상 쓸지 않고, 주어진 점을 한번에 둘 이상 지나는 경우도 없다고 가정하자.

이 때 이 가상의 직선이 평면에서 만난 점을 차례대로 둘씩 이으면 총 n/2개의 서로 교차하지 않는 선분의 쌍을 얻을 수 있다. 어떤 두 선분이 교차한다면 직선이 쓸고 가는 과정에서 어떤 한 선분을 이루는 두 점을 지나는 사이에 다른 선분의 끝점을 적어도 하나 지나가야만 하기 때문이다.

이제 이와 같은 직선을 하나 잡아 문제를 해결하자. 글쓴이는 기울기가 음의 무한대에 가까운 직선을 x축방향으로 쓰는 식으로 생각해 문제를 해결하였다.

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

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

int N;
pair<pair<int, int>, int> points[1000];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		points[i] = make_pair(make_pair(x, y), i + 1);
	}

	sort(points, points + N);

	cout << N / 2 << '\n';
	for (int i = 0; i + 1 < N; i += 2) {
		cout << points[i].second << ' ' << points[i + 1].second << '\n';
	}
}

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

이번에 볼 문제는 백준 6123번 문제인 Oh Those Fads이다.
문제는 아래 링크를 확인하자.

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

매 순간 아직 유행에 참가하지 않은 소가 있고 그 중 유행에 참가하고자 하는 소가 있는 동안 해당 소를 유행에 참가시키는 것을 반복해 문제를 해결하자.

새로 유행에 참가할 소를 빠르게 탐색하기 위해 min heap을 활용할 수 있다.

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

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

int N, K; ll L;
priority_queue<int, vector<int>, greater<>> pq;
int ans;

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

	cin >> N >> L >> K;
	while (N--) {
		int x; cin >> x;
		pq.push(x);
	}

	while (!pq.empty() && pq.top() <= L) {
		ans++;
		L += K;
		pq.pop();
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 29130번 문제인 Стеллаж с книгами이다.
문제는 아래 링크를 확인하자.

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

1부터 5까지의 정수를 사용해 모든 십자모양에는 1부터 5까지의 모든 정수가 등장하게끔, 그리고 모든 3x3 사각형의 둘레 모양에는 모든 정수가 등장하지는 않게끔 수를 배치하는 문제이다.

규칙을 하나 찾으면 위의 조건을 만족하게끔 수를 항상 규칙적으로 배치할 수 있다. 그 방법을 직접 찾아 문제를 해결해보자. (찾기 어렵다면 아래의 제출 코드를 참고하자.)

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

#include <iostream>
using namespace std;

int R, C;
int ans[5][5];

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

	ans[0][0] = 5, ans[0][1] = 4, ans[0][2] = 1, ans[0][3] = 3, ans[0][4] = 2;
	ans[1][0] = 3, ans[1][1] = 2, ans[1][2] = 5, ans[1][3] = 4, ans[1][4] = 1;
	ans[2][0] = 4, ans[2][1] = 1, ans[2][2] = 3, ans[2][3] = 2, ans[2][4] = 5;
	ans[3][0] = 2, ans[3][1] = 5, ans[3][2] = 4, ans[3][3] = 1, ans[3][4] = 3;
	ans[4][0] = 1, ans[4][1] = 3, ans[4][2] = 2, ans[4][3] = 5, ans[4][4] = 4;

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cout << ans[r % 5][c % 5] << ' ';
		}
		cout << '\n';
	}
}

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

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

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

주어지는 문자열의 집합의 원소 중 그 문자열의 ROT13 또한 집합에 들어있는 원소의 수를 (중복없이) 구하는 문제이다.

set 자료구조를 이용해 중복없이 문자열들을 다뤄 문제를 해결해주자.

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

#include <iostream>
#include <string>
#include <set>
using namespace std;

int N, slen;
char rot13[128];
set<string> st1, st2;
int ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    for (char i = 'a'; i < 'n'; i++) rot13[i] = i + 13;
    for (char i = 'n'; i <= 'z'; i++) rot13[i] = i - 13;
    
    cin >> N;
    while (N--) {
        string s;
        cin >> s;
        if (s[0] < 'n') st1.insert(s);
        else st2.insert(s);
    }
    
    for (auto x:st1){
        for (auto& l:x) l = rot13[l];
        if (st2.count(x)) ans += 2;
    }
    
    cout << ans;
}